Number of Lines To Write String: Greedy Line Filling

LeetCode 806, Number of Lines To Write String, asks you to simulate writing a string onto lines that each hold at most 100 pixels. You are given an array widths where widths[0] is the width of 'a', widths[1] is the width of 'b', and so on up to widths[25] for 'z'. Given a string s, figure out how many lines you need and how wide the last line is.

The problem

You have a widths array of 26 integers (one per lowercase letter) and a string s. You write the characters of s from left to right onto lines. Each line can hold at most 100 pixels. When adding the next character would push the current line past 100 pixels, you move to a new line and place that character there instead.

Return [lines, lastLineWidth] where lines is the total number of lines used and lastLineWidth is the width of the final line in pixels.

For example, with 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] and s = "abcdefghijklmnopqrstuvwxyz", every character is 10 pixels wide. You fit 10 characters per line (10 * 10 = 100), so you need 3 lines. The last line holds 6 characters (60 pixels). The answer is [3, 60].

The approach

This is a greedy simulation. You walk through the string character by character, keeping track of two things: how many lines you have used so far, and how many pixels the current line has consumed.

For each character, you look up its width. If the current line width plus this character's width would exceed 100, you move to a new line and reset the current width. Then you add the character's width to the current line.

That is the entire algorithm. There is no optimization trick, no data structure to maintain. You just simulate the process exactly as described.

def numberOfLines(widths, s):
    lines = 1
    current_width = 0

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

    return [lines, current_width]

The loop processes each character in order. ord(ch) - ord('a') converts the character to an index into the widths array. If placing the character on the current line would exceed 100, you increment lines and reset current_width to 0 before adding the character's width.

Step-by-step walkthrough

Here is the algorithm running on a string with varied character widths. Watch how characters fill each line and a new line starts whenever the next character would push the total past 100.

Each character is placed greedily on the current line. The moment it would not fit, a new line begins. After the last character, the values of lines and current_width give you the answer directly.

Complexity analysis

You iterate through the string once. Each character requires a constant-time lookup into the widths array and a comparison. No extra data structures are needed.

The building blocks

Greedy line filling

The core technique is greedy packing: fit as much as you can on the current line before starting a new one. This same pattern appears in text justification problems, bin packing, and any scenario where you fill a container up to a capacity and then move to the next container. The key check is always the same: "does the next item fit in the remaining space?"

Single-pass simulation

Many easy problems boil down to a single pass through the input while maintaining a small amount of state. Here, the state is just two integers: the line count and the current line width. You process each element once, update the state, and the answer is waiting for you at the end. This pattern shows up in problems like Gas Station, Best Time to Buy and Sell Stock, and Running Sum of 1d Array.

Edge cases

• Every character has width 100. Each character takes an entire line by itself. The answer is [len(s), 100] since every line holds exactly one character.
• All characters have width 1. You fit 100 characters per line. The number of lines is ceil(len(s) / 100) and the last line width is len(s) % 100 (or 100 if it divides evenly).
• Single character string. The answer is always [1, widths[ord(s[0]) - ord('a')]]. One line, one character.

From understanding to recall

This problem is simple enough that you can solve it in a few minutes once you see the pattern. But the greedy line-filling technique is a building block that shows up in harder problems like text justification and task scheduling. Practicing it in isolation, where the logic is clean and there are no distractions, helps you recognize the pattern instantly when it appears inside a more complex problem. Spaced repetition locks that recognition into long-term memory so you do not have to re-derive it each time.

Related posts

• String Compression - Linear string processing
• Add Strings - Character-by-character processing
• License Key Formatting - String formatting with constraints