LeetCode 806: Number of Lines To Write String

Problem Restatement

We are given a string s containing only lowercase English letters.

We are also given an array widths of length 26, where:

widths[0]  # width of 'a'
widths[1]  # width of 'b'
widths[25] # width of 'z'

Each line can contain at most 100 pixels.

We write the characters of s from left to right. For each character, if it fits on the current line, we add it there. If it would make the current line exceed 100 pixels, we start a new line and place the character on that new line.

Return:

[number_of_lines, width_of_last_line]

The official statement asks for the total number of lines and the width of the last line after writing the whole string.

Input and Output

Examples

Example 1:

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"

Every character has width 10.

Each line can hold 10 characters because:

10 * 10 = 100

So the lines are:

abcdefghij
klmnopqrst
uvwxyz

The last line has 6 characters, so its width is:

6 * 10 = 60

The answer is:

[3, 60]

Example 2:

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"

Here, 'a' has width 4, and every other letter has width 10.

The first line can contain:

bbbcccdddaa

Its width is:

9 * 10 + 2 * 4 = 98

The last 'a' cannot fit on the first line because:

98 + 4 = 102

So it starts a second line.

The answer is:

[2, 4]

First Thought: Direct Simulation

The problem describes a process. We can simulate that process exactly.

Keep two variables:

Start with:

lines = 1
current_width = 0

Then process each character in s.

For each character, get its width. If adding it keeps the current line at most 100, add it to the current line.

Otherwise, start a new line.

Key Insight

There is no need for dynamic programming or backtracking.

The writing rule is greedy by definition: write as many letters as possible on the current line before moving to the next line.

So each character has only one correct place:

1. Current line, if it fits.
2. Next line, if it does not fit.

Algorithm

For each character ch in s:

1. Convert ch to an index:

index = ord(ch) - ord("a")

2. Read its width:

width = widths[index]

3. If it fits on the current line:

current_width + width <= 100

then add it:

current_width += width

4. Otherwise, start a new line:

lines += 1
current_width = width

Return:

[lines, current_width]

Correctness

The algorithm processes the string from left to right, exactly as required by the problem.

For each character, it checks whether placing that character on the current line would keep the line width at most 100.

If yes, the problem rule says the character should be written on the current line, so the algorithm adds its width to current_width.

If no, the character cannot be written on the current line without exceeding the limit. The problem rule says writing must continue on the next line, so the algorithm increments lines and starts the new line with the current character.

After every character, lines is the number of lines used so far, and current_width is the width of the current last line. Therefore, after all characters are processed, returning [lines, current_width] gives the required result.

Complexity

Let n = len(s).

The widths input array has fixed size 26, so it does not affect asymptotic space.

Implementation

class Solution:
    def numberOfLines(self, widths: list[int], s: str) -> list[int]:
        lines = 1
        current_width = 0

        for ch in s:
            width = widths[ord(ch) - ord("a")]

            if current_width + width <= 100:
                current_width += width
            else:
                lines += 1
                current_width = width

        return [lines, current_width]

Code Explanation

We start with one line:

lines = 1
current_width = 0

The string is non-empty, so at least one line will be used.

For each character, we find its width:

width = widths[ord(ch) - ord("a")]

The expression ord(ch) - ord("a") maps:

'a' -> 0
'b' -> 1
...
'z' -> 25

If the character fits, we keep writing on the same line:

if current_width + width <= 100:
    current_width += width

If it does not fit, we move to a new line:

else:
    lines += 1
    current_width = width

The new line starts with the current character, so current_width becomes width.

Finally, return both values:

return [lines, current_width]

Testing

def run_tests():
    s = Solution()

    assert s.numberOfLines(
        [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],
        "abcdefghijklmnopqrstuvwxyz"
    ) == [3, 60]

    assert s.numberOfLines(
        [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],
        "bbbcccdddaaa"
    ) == [2, 4]

    assert s.numberOfLines(
        [10] * 26,
        "abcdefghij"
    ) == [1, 100]

    assert s.numberOfLines(
        [10] * 26,
        "abcdefghija"
    ) == [2, 10]

    assert s.numberOfLines(
        [2] * 26,
        "a"
    ) == [1, 2]

    print("all tests passed")

run_tests()