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 <= 1000s contains only lowercase English letters.In this approach, we iterate over the string and keep track of the width of the current line. When adding another character exceeds the allowed line width of 100 pixels, we start a new line. We store the total number of lines and the width of the last line.
We start by initializing totalLines to 1 and currentWidth to 0. As we iterate through each character in the string s, we fetch its corresponding width from the widths array. If adding a character would make the current line exceed 100 pixels, we increment the totalLines and reset currentWidth. Otherwise, we add the character's width to currentWidth.
C++
Java
Python
C#
JavaScript
The time complexity of this approach is O(n), where s. The space complexity is O(1), as we are only using a fixed amount of extra space.
This approach takes the prefix summed widths of the string. For each new position, the difference between the prefix sums represents the total width of characters up to that position. Using this information, we determine how many characters fit into each line under the given constraints, thereby expanding calculation efficiency.
In this solution, we first compute a prefix sum array where prefixSum[i] contains the total width of the first i characters. We then iterate through the prefix sum to determine where the line widths exceed 100, marking new line starts and updating currentWidth.
C++
Java
Python
C#
JavaScript
The time complexity is O(n) for constructing the prefix sum and iterating through it. The space complexity is O(n) due to the prefix sum array.
| Approach | Complexity |
|---|---|
| Greedy Approach | The time complexity of this approach is O(n), where |
| Prefix Sum Approach | The time complexity is O(n) for constructing the prefix sum and iterating through it. The space complexity is O(n) due to the prefix sum array. |
Longest Common Prefix - Leetcode 14 - Python • NeetCode • 217,791 views views
Watch 9 more video solutions →Practice Number of Lines To Write String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor