LeetCode 806 - Number of Lines To Write String

Difficulty: 🟢 Easy
Topics: Array, String

Solution

Problem Understanding

This problem is asking us to determine how to write a string s on multiple lines when each character has a specific pixel width and no line can exceed 100 pixels. We are given an array widths of length 26, where each index corresponds to a lowercase English letter, and its value indicates how many pixels wide that letter is. The goal is to compute two things: the total number of lines needed to write the entire string, and the width in pixels of the last line.

The input s is a string containing only lowercase letters, and its length ranges from 1 to 1000. The widths array contains integers between 2 and 10, which are small and fixed. The output is an array of length 2, where the first element is the number of lines, and the second is the width of the last line.

Edge cases that could trip a naive implementation include strings where every character is near the maximum width of 10, which could require frequent line breaks, or strings consisting entirely of a single letter with width 2 or 10. The problem guarantees that widths has exactly 26 elements and that s only contains lowercase letters, so we do not need to handle invalid characters or out-of-bounds indices.

Approaches

The brute-force approach is straightforward: we iterate through each character in the string s, look up its width in widths, and add it to a running total for the current line. Whenever this running total exceeds 100, we increment the line count and reset the running total to the current character's width. This approach works correctly because it simulates the writing process exactly as described in the problem. Its complexity is acceptable here due to the constraints, but conceptually it is less efficient because it does not leverage any precomputation or optimization.

The optimal approach is essentially the same as the brute-force approach in this problem because each character must be processed individually to determine if it fits on the current line. The key observation is that we do not need any extra data structures beyond a simple counter for the current line width and a counter for the number of lines. This minimizes space usage and simplifies implementation.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Iterate through string and sum widths, breaking lines as needed
Optimal	O(n)	O(1)	Same as brute-force; no extra memory is required beyond counters

Algorithm Walkthrough

Initialize a variable lines to 1, representing the first line. Initialize current_width to 0, representing the width used on the current line.
Iterate through each character ch in the string s. For each character, calculate its width by indexing into the widths array using ord(ch) - ord('a').
Check if adding this character's width to current_width would exceed 100 pixels. If it does, increment lines by 1 and reset current_width to the width of the current character.
If adding the character does not exceed 100 pixels, simply increment current_width by the character's width.
After processing all characters, return [lines, current_width], where lines is the total number of lines used and current_width is the width of the last line.

Why it works: The algorithm maintains an invariant that current_width is always the width of the current line. Whenever a character does not fit, a new line is started. This guarantees that no line exceeds 100 pixels, and all characters are accounted for exactly once.

Python Solution

from typing import List

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

        for ch in s:
            ch_width = widths[ord(ch) - ord('a')]
            if current_width + ch_width > 100:
                lines += 1
                current_width = ch_width
            else:
                current_width += ch_width

        return [lines, current_width]

The Python implementation follows the algorithm step by step. We initialize counters for lines and the current line width. For each character, we determine its width and decide whether to continue on the current line or start a new one. Finally, we return the total number of lines and the width of the last line.

Go Solution

func numberOfLines(widths []int, s string) []int {
    lines := 1
    currentWidth := 0

    for _, ch := range s {
        chWidth := widths[ch-'a']
        if currentWidth + chWidth > 100 {
            lines++
            currentWidth = chWidth
        } else {
            currentWidth += chWidth
        }
    }

    return []int{lines, currentWidth}
}

In Go, we use a for loop over the string, which gives us runes. We subtract 'a' to get the index into widths. Integer arithmetic works the same as Python here, and we return a slice containing the results. No special handling for empty strings is needed because the constraints guarantee at least one character.

Worked Examples

Example 1: s = "abcdefghijklmnopqrstuvwxyz" with widths = [10]*26

Character	Width	Current Width	Lines
a-j	10	100	1
k-t	10	100	2
u-z	10	60	3

Output: [3, 60]

Example 2: s = "bbbcccdddaaa" with widths = [4,10,...] (b=10, c=10, d=10, a=4)

Character	Width	Current Width	Lines
bbbcccddd	10/10/10...	98	1
aa	4	4	2

Output: [2, 4]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character in `s` is visited once to determine its width and update counters
Space	O(1)	Only two integer counters are used; no extra space scales with input size

The time complexity is linear because we must examine every character. Space complexity is constant since no additional data structures dependent on input size are used.

Test Cases

# Provided examples
assert Solution().numberOfLines([10]*26, "abcdefghijklmnopqrstuvwxyz") == [3, 60]  # example 1
assert Solution().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]  # example 2

# Edge cases
assert Solution().numberOfLines([10]*26, "a"*10) == [1, 100]  # exactly fills one line
assert Solution().numberOfLines([10]*26, "a"*11) == [2, 10]  # slightly over one line
assert Solution().numberOfLines([2]*26, "a"*50) == [1, 100]  # many small letters
assert Solution().numberOfLines([2]*26, "a"*51) == [2, 2]  # many small letters overflow

# Single character string
assert Solution().numberOfLines([5]*26, "z") == [1, 5]  # minimal string

# All letters same width less than 100
assert Solution().numberOfLines([5]*26, "abcde"*20) == [5, 100]  # multiple lines exact fit

Test	Why
Single character string	Validates minimal input
Strings that exactly fill lines	Ensures correct line count when width == 100
Strings that overflow by 1 character	Checks correct line incrementing
Many small letters	Verifies algorithm handles multiple small widths efficiently
Provided examples	Validates correctness against problem statement

Edge Cases

One important edge case is a string consisting entirely of the smallest width letters. If the width is 2 and the string is 1000 characters long, this requires many lines, but the algorithm handles it because it increments lines whenever 100 pixels are reached, regardless of the number of characters.

Another edge case is a string where every character has the maximum width of 10. In this case, lines will almost always contain exactly 10 characters, and the last line may have fewer. The algorithm still correctly starts a new line when adding the next character would exceed 100.

Finally, strings where the last line is exactly 100 pixels wide could be tricky if the algorithm does not properly reset current_width after filling a line. Our implementation correctly updates current_width when a line is full, ensuring that the last line width reflects the remaining characters accurately.