algoadvance

You are given a list widths, where widths[0] is the width of 'a', widths[1] is the width of 'b', and so on up to widths[25] which is the width of 'z'. You are also given a string S.

Write a function numberOfLines(widths, S) that returns two integers: the number of lines needed to write the string S and the width of the last line. The width of each line must not exceed 100 units.

Clarifying Questions

  1. Are the widths always guaranteed to be positive integers and less than 100?
    • Yes, each character’s width is a positive integer and is reasonably small compared to the line width capacity of 100 units.
  2. Can the input string S be empty?
    • For simplicity, consider that the input string S is non-empty.
  3. Is it guaranteed that the total width of the input string can be distributed over multiple lines?
    • Yes, however, each individual character will always fit within the 100 units constraint.

Strategy

  1. Initialize counters for the number of lines used (lines) and the current width of the last line (current_width).
  2. Iterate through each character in the string S.
  3. For each character, determine its width using the widths list.
  4. Check if adding the current character’s width to current_width will exceed the limit of 100 units.
    • If yes, increment lines by 1 and reset current_width to the current character’s width.
    • If no, add the character’s width to current_width.
  5. After processing all characters, return the number of lines used and the width of the last line.

Code

def numberOfLines(widths, S):
    lines, current_width = 1, 0
    
    for char in S:
        char_width = widths[ord(char) - ord('a')]
        if current_width + char_width > 100:
            lines += 1
            current_width = char_width
        else:
            current_width += char_width
    
    return [lines, current_width]

# Example usage
widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = "abcdefghijklmnopqrstuvwxyz"
print(numberOfLines(widths, S))  # Output: [3, 60]

Time Complexity

The time complexity of this solution is O(n), where n is the length of the string S. Each character in the string is visited exactly once.

The space complexity is O(1) since we are using a fixed amount of extra space regardless of the input size. The widths list is always of constant size 26, and we only use a few additional variables for counting.

Try our interview co-pilot at AlgoAdvance.com