0

Fewest lines to wrap a sentence

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Fewest lines to wrap a sentence

Companies: Google

Difficulty: Easy

Problem statement

Given a non-empty string text and a positive integer max_width, return the fewest lines needed to lay out all the words of text.

Implement:

def count_lines(text: str, max_width: int) -> int: ...

Rules:

  • A word is a run of non-space characters. Extra spaces in text (leading, trailing or repeated) do not matter.
  • Words keep their original order. You only choose where each line ends.
  • Words on the same line are separated by exactly one space. A line's length is the sum of its word lengths plus one per gap.
  • No line may be longer than max_width, with one exception: a word longer than max_width is placed on a line by itself and may overflow. It is never split.

Constraints: 1 <= len(text) <= 10^6, 1 <= max_width <= 10^6.

Example 1

text = "the quick brown fox jumps", max_width = 10
→ 3

The lines are the quick (9), brown fox (9) and jumps (5).

Example 2

text = "hi extraordinary yo", max_width = 5
→ 3

extraordinary is longer than 5, so it takes its own line: hi / extraordinary / yo.

Approach

Clarify first. Ask these before writing code:

  • What counts as a word? Words are runs of non-space characters. Leading, trailing and repeated spaces in the input carry no meaning, so split on whitespace.
  • Line length. A line of words w1 .. wk has length len(w1) + ... + len(wk) + (k - 1), one space between neighbors and none at the ends.
  • Order is fixed. Words stay in their original order. You only choose where the line breaks go.
  • Words longer than the width. Such a word gets a line of its own. It is never split and never shares a line. This is the one rule that is easy to get wrong.
  • Empty input. The task says text is non-empty, but ask whether all-whitespace input is possible. Zero lines is the natural answer.

Brute force. Try every way to place line breaks between words (2^(n-1) ways), keep the valid ones, and take the fewest lines. A DP over "fewest lines for the first i words" brings it to O(n^2). Both are correct, but neither is needed.

Optimal: greedy packing. Walk the words once. Keep used, the length of the current line, or 0 if no line is open.

  1. If the word is longer than max_width: close the open line if there is one, then count one line for this word alone, and leave no line open.
  2. Else if no line is open: open a new line with this word (used = len(word)).
  3. Else if used + 1 + len(word) <= max_width: add it to the current line.
  4. Else: close the current line and open a new one with this word.

At the end, count the open line if there is one.

Why greedy is optimal. Compare greedy with any valid layout, line by line. Claim: after j lines, greedy has placed at least as many words as the other layout. It holds for j = 0. Suppose greedy is ahead or level after j lines. The other layout's line j + 1 holds some words a .. b that fit. Greedy's line j + 1 starts at or after a. Any suffix of a line that fits also fits, so greedy can reach at least b, and it takes every word that fits. Oversize words do not break this: both layouts must put them alone. So greedy never needs more lines than any other layout.

Invariant. Before each word, used is 0 (no open line) or the exact length of the open line, and the open line is always <= max_width. lines counts the closed lines only.

Code

from __future__ import annotations


def count_lines(text: str, max_width: int) -> int:
    """Fewest lines needed to lay out the words of text.

    Words are separated by one space and keep their order. A line may not be
    longer than max_width, except a word longer than max_width, which takes
    a line on its own.
    """
    if max_width < 1:
        raise ValueError("max_width must be positive")

    lines = 0  # closed lines
    used = 0   # length of the open line, 0 if none is open

    for word in text.split():
        n = len(word)
        if n > max_width:
            if used:
                lines += 1
            lines += 1  # the oversize word alone
            used = 0
        elif used == 0:
            used = n
        elif used + 1 + n <= max_width:
            used += 1 + n
        else:
            lines += 1
            used = n

    return lines + (1 if used else 0)


def wrap(text: str, max_width: int) -> list[str]:
    """The lines that count_lines counts, for checking and for follow-ups."""
    if max_width < 1:
        raise ValueError("max_width must be positive")

    result: list[str] = []
    current: list[str] = []
    used = 0

    for word in text.split():
        n = len(word)
        if n > max_width:
            if current:
                result.append(" ".join(current))
            result.append(word)
            current, used = [], 0
        elif not current:
            current, used = [word], n
        elif used + 1 + n <= max_width:
            current.append(word)
            used += 1 + n
        else:
            result.append(" ".join(current))
            current, used = [word], n

    if current:
        result.append(" ".join(current))
    return result


def min_width_for_lines(text: str, max_lines: int) -> int:
    """Follow-up: the smallest width that fits text in at most max_lines lines."""
    words = text.split()
    if not words:
        return 0
    lo = max(len(w) for w in words)          # no word may overflow
    hi = sum(len(w) for w in words) + len(words) - 1  # everything on one line
    while lo < hi:
        mid = (lo + hi) // 2
        if count_lines(text, mid) <= max_lines:
            hi = mid
        else:
            lo = mid + 1
    return lo


if __name__ == "__main__":
    assert count_lines("the quick brown fox jumps", 10) == 3
    assert wrap("the quick brown fox jumps", 10) == ["the quick", "brown fox", "jumps"]
    assert count_lines("a b c", 5) == 1
    assert count_lines("a b c", 4) == 2
    assert count_lines("hi extraordinary yo", 5) == 3
    assert wrap("hi extraordinary yo", 5) == ["hi", "extraordinary", "yo"]
    assert count_lines("extraordinary", 3) == 1
    assert count_lines("  spaced   out  ", 20) == 1
    assert count_lines("   ", 4) == 0
    assert count_lines("ab cd", 5) == 1
    assert min_width_for_lines("the quick brown fox jumps", 2) == 15
    for t, w in [("one two three four five six", k) for k in range(1, 30)]:
        assert count_lines(t, w) == len(wrap(t, w))
    print("ok")

Complexity

  • count_lines: O(L) time, where L is the length of text, because splitting reads every character once and each word is handled in O(1). Extra space is O(L) for the split word list. A hand-written scanner that measures word lengths in place brings extra space to O(1).
  • wrap: O(L) time and O(L) space for the output.
  • min_width_for_lines: O(L log L) time, a binary search over widths up to L with one O(L) count per step.

Test cases

  • "the quick brown fox jumps", width 10 → 3 (the quick / brown fox / jumps).
  • "a b c", width 5 → 1 (the line is exactly 5 long, which is allowed).
  • "a b c", width 4 → 2 (a b / c).
  • "ab cd", width 5 → 1 (exact fit including the space).
  • "hi extraordinary yo", width 5 → 3: the long word closes hi and sits alone, and yo starts a fresh line.
  • "extraordinary", width 3 → 1 (a lone oversize word).
  • " spaced out ", width 20 → 1 (extra spaces are ignored).
  • " ", width 4 → 0 (no words).
  • Width 1 with "a b c" → 3.
  • Large input: 10^6 one-letter words with width 1_000_000 → 1; check the solution stays linear.

Follow-ups

  1. Return the lines, not just the count. Use wrap above. Same greedy, but collect each line's words and join them with single spaces.
  2. Full justification (LeetCode 68 style). After greedy picks each line's words, spread the leftover spaces between gaps, extra spaces going to the leftmost gaps; the last line and one-word lines are left-aligned. Greedy line choice does not change; only the rendering does.
  3. Hyphenate or split long words. Instead of letting a word overflow, cut it into chunks of max_width (or max_width - 1 plus a hyphen). Each full chunk is its own line, and the last chunk can start a line that later words join. The count becomes ceil(len / width) lines for the chunks plus the usual packing.
  4. Fewest lines given a page width is easy, now give the smallest width for at most k lines. The line count is non-increasing in width, so binary search the width between the longest word and the one-line length (min_width_for_lines).
  5. Make it look good (minimum raggedness). Greedy minimizes lines but can leave one very short line. Minimizing the sum of squared trailing space needs DP: best[i] = min over j of best[j] + cost(j..i-1), O(n^2) or O(n * W) with the width bound. The last line usually costs nothing. This is the Knuth-Plass idea.

Interviewer expectations

Mid-level (L4)

  • Asks how spaces and oversize words are handled before coding.
  • Writes the single-pass greedy with correct + 1 space accounting and the final open line counted.
  • Tests the exact-fit and oversize-word cases.

Senior (L5)

  • Explains why greedy is optimal (the "stays ahead" argument), not just that it passes examples.
  • Handles oversize words cleanly, including closing the current line first, and empty or all-space input.
  • Moves quickly to returning lines and to full justification without restructuring the code.

Staff (L6+)

  • Separates choosing breaks from rendering lines, so justification, hyphenation and different spacing rules plug in.
  • Spots that greedy is wrong for "looks good" and explains the DP, its cost, and when that cost matters.
  • Raises real text concerns: Unicode display width (wide characters, combining marks), tabs, and streaming very large input without holding it all in memory.

Sign in to comment, vote or remix.