806. Number of Lines To Write String
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 1
Acceptance rate: 65.5%
Problem Breakdown
We are given a string s consisting of lowercase English letters and an array widths where each element represents the width in pixels of the corresponding letter (‘a’ to ‘z’). The task is to write the string across multiple lines such that no line exceeds 100 pixels in width. We need to return an array with two elements: the total number of lines used and the width of the last line.
Inputs:
widths: An array of integers where each integer represents the pixel width of a letter from ‘a’ to ‘z’.s: A string of lowercase English letters.
Outputs:
- An array of two integers:
- The first integer is the total number of lines used.
- The second integer is the width of the last line in pixels.
Implicit Constraints/Edge Cases:
- The input string
scan be empty, which would result in zero lines and a width of zero for the last line. - Each character in
swill always be a lowercase English letter. - The sum of widths for any substring should not exceed 100 pixels per line.
Intuition
A brute-force approach would involve iterating through each character in the string, adding its width to a running total until the total exceeds 100 pixels. At that point, we start a new line and reset the running total. This approach is straightforward but not optimal in terms of time complexity since it involves multiple passes over the string.
The key insight is to realize that we can determine the number of lines and the width of the last line in a single pass through the string by maintaining a running total of the current line’s width. If adding the next character would exceed 100 pixels, we increment the line count and reset the running total.
Approach
- Initialize two variables:
linesto count the number of lines (starting at 1 since we always have at least one line) andcurrent_widthto track the width of the current line. - Iterate through each character in the string
s. - For each character, determine its width using the
widthsarray. - If adding this character’s width to
current_widthwould exceed 100 pixels:- Increment the
linescounter. - Reset
current_widthto the width of the current character.
- Increment the
- If adding the character’s width does not exceed 100 pixels, simply add it to
current_width. - After processing all characters, return an array with
linesandcurrent_width.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string
s. We make a single pass through the string. - Space Complexity: O(1). We use a constant amount of extra space regardless of the input size.
Solution
def numberOfLines(widths, s):
lines = 1
current_width = 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]
Edge Cases Handled
- Empty String (
s = ""): The function returns[1, 0]since there are no characters to process, but we still have one line with zero width. - Single Character Strings: The function correctly handles strings of length 1 by returning
[1, width_of_character]. - Strings Where All Characters Fit on One Line: If the sum of all character widths is less than or equal to 100, the function returns
[1, total_width]. - Strings That Require Multiple Lines: The function correctly increments the line count and resets
current_widthwhen necessary.