Since November I have been solving LeetCode problems, and during this time I’ve gained an appreciation for what it takes to write these types of problems. It turns out that it is more difficult to write some of these problems than to solve them. Since I most recently covered dynamic programming, I thought I would throw my hat into the ring by writing a problem about my favorite dynamic programming algorithm: Knuth-Plass line breaking. Here is this problem in the format of a LeetCode question.

Optimal Line Breaks

Description

Given a list of words, an ideal line length, and a maximum line length, split the words into lines that minimize a total penalty score. Words on a line are joined by single spaces, and a line’s length is the resulting character count.

Each line except the last is scored (ideal_length - line_length)^2 if the line fits within max_length, or $\infty$ if it doesn’t. The last line always scores 0.

Return the line breaks with the minimum total score as a list of strings, one for each line. If there is a tie between multiple line breaks, choose the earliest breakpoints.

Constraints

1 <= len(words) <= 900
1 <= len(word) <= max_length for every word
1 <= ideal_length <= max_length <= 200

Examples

Example 1

Input:  words = ["hello", "world"],
        ideal_length = 20,
        max_length = 25
Output: ["hello world"]

Explanation: All words fit on a single line: hello world has length 11. As the only (last) line, it scores 0. Total score = 0.

Example 2

Input:  words = ["the", "quick", "brown", "fox"],
        ideal_length = 10,
        max_length = 12
Output: ["the quick", "brown fox"]

Explanation:

Line 1: the quick (length 9). Score = $(10 - 9)^2 = 1$ .
Line 2: brown fox (length 9). Last line, score = 0.
Total score = 1.

Example 3

Input:  words = ["the", "quick", "brown", "fox"],
        ideal_length = 11,
        max_length = 15
Output: ["the quick", "brown fox"]

Explanation:

Line	Length	Score
`the quick`	9	$(11-9)^2 = 4$
`brown fox`	9	0 (last)

Total score = 4.

Signature

def optimal_line_breaks(words: list[str], ideal_length: int, max_length: int) -> list[str]:
    pass

Optimal Line Breaks: Editorial

Summary

This problem is a simplified version of the Knuth-Plass line-breaking algorithm, which is the algorithm used by TeX to format paragraphs. The full Knuth-Plass algorithm, described in the original paper, handles proportional fonts, “glue” (stretchable spaces), and non-rectangular paragraph shapes. Our problem strips all of that away and asks only: given monospaced text, an ideal line length, and a maximum line length, find the line breaks that minimize total penalty.

Approach 1: Greedy

Intuition

The natural first attempt is the greedy algorithm: pack as many words onto each line as possible without exceeding max_length, then start a new line. This is what most text editors and word processors do.

The idea is simple: fill each line as full as possible, then start a new line. Each line ends up as long as it can be, with only the last line potentially much shorter.

def greedy_line_breaks(words, max_length):
    lines = []
    line_words = []
    line_length = 0
    for word in words:
        new_length = line_length + (1 if line_length > 0 else 0) + len(word)
        if new_length > max_length and line_words:
            lines.append(" ".join(line_words))
            line_words = []
            line_length = 0
        line_words.append(word)
        line_length += (1 if line_length > 0 else 0) + len(word)
    if line_words:
        lines.append(" ".join(line_words))
    return lines

Why greedy fails

The greedy algorithm doesn’t know about ideal_length at all – it only considers max_length. This means it greedily packs words onto a line, potentially leaving very short lines later.

Consider Example 3 from the problem statement:

words = ["the", "quick", "brown", "fox"]
ideal_length = 11
max_length = 15

The greedy algorithm packs as many words as it can onto line 1:

Line	Length	Score
`the quick brown`	15	$(11 - 15)^2 = 16$
`fox`	3	0 (last line)

Total greedy score = 16.

But we can do better. If we break earlier – after just two words – the penalty drops sharply:

Line	Length	Score
`the quick`	9	$(11 - 9)^2 = 4$
`brown fox`	9	0 (last line)

Total optimal score = 4.

By greedily stuffing brown onto line 1, the greedy algorithm overshoots the ideal by 4 characters. The optimal solution instead distributes words more evenly, and the last line (which is free) absorbs the slack.

Complexity

Time: $O(n)$ , where $n$ is the number of words.
Space: $O(n)$ for the output lines.

Greedy is fast, but it doesn’t minimize the penalty. We need to consider all possible break points.

Approach 2: Brute Force

Intuition

Between every pair of consecutive words, we have a choice: break or don’t break. With $n$ words there are $n - 1$ gaps, giving $2^{n-1}$ possible ways to break the paragraph into lines.

We can enumerate all of them recursively. At each word position i, we try every valid next-break position j (i.e., every line words[i..j] that fits within max_length), score that line, then recurse on the remainder words[j+1:].

import math

def brute_force_line_breaks(words, ideal_length, max_length):
    n = len(words)

    def visit(i):
        if i >= n:
            return (0, [])

        best_score = math.inf
        best_lines = []
        line_length = 0

        for j in range(i, n):
            line_length += len(words[j]) + (1 if j > i else 0)
            if line_length > max_length:
                break
            line = " ".join(words[i : j + 1])
            if j + 1 >= n:
                score = 0  # last line
                tail_lines = []
            else:
                score, tail_lines = visit(j + 1)
                score += (ideal_length - line_length) ** 2
            if score < best_score:
                best_score = score
                best_lines = [line] + tail_lines

        return (best_score, best_lines)

    return visit(0)[1]

Complexity

Time: $O(2^n)$ in the worst case: every gap is a potential break.
Space: $O(n)$ for the call stack.

This is correct but computationally infeasible for the constraint $n \le 900$ .

Approach 3: Dynamic Programming

Intuition

Imagine we have a long list of words, stretching far to the left and right. We’re looking somewhere in the middle, and we assert that a new line starts at the caret (^):

... having little or no money in my purse and nothing particular to interest me on ...
                                             ^

We don’t know yet whether this is a good break point. But suppose we commit to it and ask: what’s the best way to break the words on either side? An important fact emerges: the left side and the right side can be solved independently. Nothing about how we broke the words to the left of the caret affects the best way to break the words to the right.

Now imagine we place a second caret somewhere to the right of the first:

... having little or no money in my purse and nothing particular ... me on shore I thought I would sail ...
                                             ^                                  ^

The same independence holds. The subproblem between the two carets and the subproblem to the right of the second caret can each be solved on their own. If we keep placing carets further and further to the right, we’ll eventually reach a subproblem near the end of the paragraph:

... the watery part of the world
   ^

If this remainder is shorter than the maximum line width, then it’s trivially solved: it’s the last line, and it scores 0. We can just write down the answer. Even if we shifted the caret one word to the right, the answer would still be trivial: it’s still just the tail of the paragraph.

Now here’s the key: suppose we back the caret up a bit and look at a slightly larger subproblem:

... I thought I would sail about a little and see the watery part of the world
     ^                                       ^

The chunk to the right of the second caret is a subproblem we’ve already solved. We don’t need to re-solve it – we just look up its score. So finding the best break for the chunk starting at the first caret reduces to trying each possible position for the second caret and picking whichever gives the lowest combined score.

This is the core DP insight: for any given position in the word list, there is exactly one best score for the suffix starting there. Once we’ve computed it, we never recompute it. If we start at the end of the paragraph and work backwards, we can find:

the best “tail” (trivial – it’s the last line),
then the best “one line + tail” (try each break point, look up the tail),
then the best “one line + one line + tail”,
and so forth, all the way back to the beginning.

More precisely, this gives us two properties:

Optimal substructure: the optimal solution for the full paragraph contains within it the optimal solution for every suffix.
Overlapping subproblems: many different left-side break choices lead to the same suffix subproblem. For example, whether line 1 ends at word 3 or word 4, both choices eventually need the optimal solution for words[5:].

Recurrence relation

Define cost(i) as the minimum total penalty for breaking words[i:] into lines. Let len(i, j) be the length of the line formed by joining words[i], words[i+1], ..., words[j-1] with single spaces.

Base case:

\text{cost}(n) = 0

General case:

\text{cost}(i) = \min_{\substack{i < j \le n \\ \text{len}(i,j) \le \text{max\_length}}} \text{line\_cost}(i, j) + \text{cost}(j)

where

\text{line\_cost}(i, j) = \begin{cases} 0 & \text{if } j = n \text{ (last line)} \\ (\text{ideal\_length} - \text{len}(i, j))^2 & \text{otherwise} \end{cases}

The answer to the original problem is $\text{cost}(0)$ : the minimum penalty for breaking all the words into lines.

Implementation

import math

def optimal_line_breaks(words, ideal_length, max_length):
    n = len(words)
    memo = {}

    def cost(i):
        """Returns (best_score, next_break_index) for words[i:]."""
        if i >= n:
            return (0, n)
        if i in memo:
            return memo[i]

        line_length = 0
        best_score = math.inf
        best_j = i + 1

        for j in range(i, n):
            # Add word j to the current line starting at i.
            line_length += len(words[j]) + (1 if j > i else 0)

            if line_length > max_length:
                break

            # If there are no more words, this is the last line and
            # scores 0.
            if j + 1 >= n:
                score = 0  # last line scores 0
            else:
                tail_score = cost(j + 1)[0]
                score = (ideal_length - line_length) ** 2 + tail_score

            if score < best_score:
                best_score = score
                best_j = j + 1

        memo[i] = (best_score, best_j)
        return memo[i]

    cost(0)

    # Reconstruct lines from the memo table.
    lines = []
    pos = 0
    while pos < n:
        next_pos = memo[pos][1]
        lines.append(" ".join(words[pos:next_pos]))
        pos = next_pos

    return lines

The reconstruction step walks the memo table from position 0, following next_break_index pointers to recover the actual line strings.

Complexity

Time: $O(n \cdot w)$ , where $n$ is the number of words and $w$ is the maximum number of words that fit on a single line (bounded by max_length). Each of the $n$ states examines at most $w$ candidate break points. Since $w \le \text{max\_length} \le 200$ , this is effectively $O(200n) = O(n)$ .
Space: $O(n)$ for the memoization table, plus $O(n)$ for the call stack (which can be eliminated by computing bottom-up).

Tests

def test():
    # Example 1: Trivial (one line)
    result = optimal_line_breaks(["hello", "world"], ideal_length=20, max_length=25)
    assert result == ["hello world"], f"Example 1 failed: {result}"

    # Example 2: Small (two lines)
    result = optimal_line_breaks(
        ["the", "quick", "brown", "fox"], ideal_length=10, max_length=12
    )
    assert result == ["the quick", "brown fox"], f"Example 2 failed: {result}"

    # Additional test: seven short words
    result = optimal_line_breaks(
        ["aaa", "bbb", "cc", "dd", "eee", "fff", "gg"],
        ideal_length=8,
        max_length=10,
    )
    assert result == [
        "aaa bbb",
        "cc dd eee",
        "fff gg",
    ], f"Example 3 failed: {result}"

    # Greedy packs the first line full, leaving "fox" stranded.
    words = ["the", "quick", "brown", "fox"]
    greedy_result = greedy_line_breaks(words, max_length=15)
    optimal_result = optimal_line_breaks(words, ideal_length=11, max_length=15)
    assert greedy_result == [
        "the quick brown",
        "fox",
    ], f"greedy failed: {greedy_result}"
    assert optimal_result == [
        "the quick",
        "brown fox",
    ], f"optimal failed: {optimal_result}"

    # Brute force vs. DP on small inputs.
    small_cases = [
        (["a"], 5, 10),
        (["a", "b"], 5, 10),
        (["a", "b", "c"], 3, 5),
        (["hello"], 3, 10),
        (["hello", "world"], 5, 6),
        (["the", "quick", "brown", "fox"], 10, 12),
        (["the", "quick", "brown", "fox"], 11, 15),
        (["aa", "bb", "cc", "dd", "ee"], 5, 7),
    ]
    for words, ideal, max_len in small_cases:
        bf_result = brute_force_line_breaks(words, ideal, max_len)
        dp_result = optimal_line_breaks(words, ideal, max_len)
        assert bf_result == dp_result, (
            f"Brute force vs DP mismatch for {words}, ideal={ideal}, max={max_len}: "
            f"bf={bf_result}, dp={dp_result}"
        )

    # Longer paragraph where greedy produces uneven lines. Greedy packs
    # lines greedily, leaving short trailing lines that inflate the
    # total penalty. The optimal solution distributes words more evenly.
    words = (
        "call me ishmael some years ago never mind how long precisely "
        "having little or no money in my purse and nothing particular "
        "to interest me on shore I thought I would sail about a little "
        "and see the watery part of the world"
    ).split()
    greedy_result = greedy_line_breaks(words, max_length=40)
    optimal_result = optimal_line_breaks(words, ideal_length=36, max_length=40)
    assert greedy_result == [
        "call me ishmael some years ago never",
        "mind how long precisely having little or",
        "no money in my purse and nothing",
        "particular to interest me on shore I",
        "thought I would sail about a little and",
        "see the watery part of the world",
    ], f"greedy failed: {greedy_result}"
    assert optimal_result == [
        "call me ishmael some years ago never",
        "mind how long precisely having little",
        "or no money in my purse and nothing",
        "particular to interest me on shore I",
        "thought I would sail about a little",
        "and see the watery part of the world",
    ], f"optimal failed: {optimal_result}"

    print("All tests passed.")


if __name__ == "__main__":
    test()