Number of Lines To Write String
EasyPrompt
You are given a string s of lowercase English letters and an array widths denoting how many pixels wide each lowercase English letter is. Specifically, widths[0] is the width of 'a', widths[1] is the width of 'b', and so on.
You are trying to write s across several lines, where each line is no longer than 100 pixels. Starting at the beginning of s, write as many letters on the first line such that the total width does not exceed 100 pixels. Then, from where you stopped in s, continue writing as many letters as you can on the second line. Continue this process until you have written all of s.
Return an array result of length 2 where:
result[0]is the total number of lines.result[1]is the width of the last line in pixels.
Example 1:
Input: 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"
Output: [3,60]
Explanation: You can write s as follows:
abcdefghij // 100 pixels wide
klmnopqrst // 100 pixels wide
uvwxyz // 60 pixels wide
There are a total of 3 lines, and the last line is 60 pixels wide.Example 2:
Input: widths = [4,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 = "bbbcccdddaaa"
Output: [2,4]
Explanation: You can write s as follows:
bbbcccdddaa // 98 pixels wide
a // 4 pixels wide
There are a total of 2 lines, and the last line is 4 pixels wide.
Constraints:
widths.length == 262 <= widths[i] <= 101 <= s.length <= 1000scontains only lowercase English letters.
Approaches
1 approach with complexity analysis and trade-offs.
The problem can be solved efficiently using a single pass through the input string. This approach simulates the process of writing the string character by character, line by line, according to the given rules. We maintain a count of the lines used and the width of the current line. For each character, we check if it fits on the current line. If it does, we add its width to the current line's width. If not, we start a new line and place the character there.
Algorithm
- Initialize
linesto 1, as we always start with at least one line. - Initialize
currentWidthto 0. - Define a constant
MAX_WIDTHas 100. - Iterate through each character
cof the input strings. - For each character, determine its width by looking it up in the
widthsarray:charWidth = widths[c - 'a']. - Check if adding this character to the current line would exceed the
MAX_WIDTH.- If
currentWidth + charWidth > MAX_WIDTH, it means the character must go on a new line. Incrementlinesand resetcurrentWidthtocharWidth. - Otherwise, the character fits. Add its width to the
currentWidth:currentWidth += charWidth.
- If
- After iterating through all characters, the final values of
linesandcurrentWidthare the answer. - Return an array containing
[lines, currentWidth].
Walkthrough
This approach is a greedy simulation. We iterate through the string s once, keeping track of the number of lines used and the pixel width of the current line. We start with one line and zero width. For each character in s, we find its width from the widths array. We then check if adding this character's width to the current line's width would exceed the maximum allowed width of 100 pixels. If it would, we increment our line count and set the current line's width to be the width of the current character (as it's the first character on the new line). If it fits, we simply add the character's width to the current line's width. After processing all characters, the total number of lines and the width of the very last line are our result.
class Solution { public int[] numberOfLines(int[] widths, String s) { // The maximum width of a line. final int MAX_WIDTH = 100; // Start with one line. int lines = 1; // The width of the current line being written. int currentWidth = 0; // Iterate over each character in the string. for (char c : s.toCharArray()) { // Get the width of the current character. int charWidth = widths[c - 'a']; // Check if the character fits on the current line. if (currentWidth + charWidth > MAX_WIDTH) { // If not, start a new line. lines++; // The new line's width starts with the current character's width. currentWidth = charWidth; } else { // If it fits, add its width to the current line. currentWidth += charWidth; } } // Return the total number of lines and the width of the last line. return new int[]{lines, currentWidth}; }}Complexity
Time
O(N), where N is the length of the string `s`. We perform a single pass through the string, and each operation inside the loop (array lookup, arithmetic, comparison) takes constant time.
Space
O(1), because we only use a few variables to store the line count and current width. The space required is constant and does not depend on the size of the input string `s`.
Trade-offs
Pros
It is the most efficient solution with optimal time and space complexity.
The logic is straightforward and directly models the problem statement.
The implementation is simple and easy to understand.
Cons
There are no significant disadvantages to this approach as it is optimal in terms of both time and space complexity.
Solutions
Solution
class Solution { private static final int MAX_WIDTH = 100 ; public int [] numberOfLines ( int [] widths , String s ) { int last = 0 , row = 1 ; for ( char c : s . toCharArray ()) { int w = widths [ c - 'a' ]; if ( last + w <= MAX_WIDTH ) { last += w ; } else { ++ row ; last = w ; } } return new int [] { row , last }; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.