806. Number of Lines To Write String
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.
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 == 26
2 <= widths[i] <= 10
1 <= s.length <= 1000
s
contains only lowercase English letters.
Solutions
Solution 1: Simulation
We define two variables lines
and last
, representing the number of lines and the width of the last line, respectively. Initially, lines = 1
and last = 0
.
We iterate through the string $s$. For each character $c$, we calculate its width $w$. If $last + w \leq 100$, we add $w$ to last
. Otherwise, we increment lines
by one and reset last
to $w$.
Finally, we return an array consisting of lines
and last
.
The time complexity is $O(n)$, where $n$ is the length of the string $s$. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|