Problem Description
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.
Key Insights
- Each letter has a specific pixel width defined in the widths array.
- The maximum width for each line is capped at 100 pixels.
- The process involves iterating through the string and accumulating widths until the line limit is reached.
- The output consists of the total number of lines used and the width of the last line.
Space and Time Complexity
Time Complexity: O(n), where n is the length of the string s, since we need to traverse the string once. Space Complexity: O(1), as we are using a constant amount of additional space for counters and do not require any extra data structures.
Solution
To solve the problem, we can use a simple iterative approach. We will maintain a counter for the current width of the line and a line count. As we iterate through the string s, we will add the width of each character to the current line width. If adding a character exceeds 100 pixels, we increment the line count, reset the current width for the new line, and continue. Finally, we return the total number of lines and the width of the last line.