1. Why Greedy Word Wrapping Fails & The Knuth-Plass Badness Function
Given $n$ words of widths $w_0, w_1, \dots, w_{n-1}$ and target line width $L$, a greedy line breaker (used in basic web browsers and early word processors) packs words onto the current line until the next word exceeds $L$. This local myopia often packs $99\%$ of lines tightly and then encounters a long URL or technical identifier, leaving a massive gap on the preceding line.
In 1981, Donald Knuth and Michael Plass revolutionized digital typography in $\TeX$ by optimizing global paragraph demerits across all lines simultaneously:
- The width of placing words $i \dots j-1$ on a single line (with 1 unit space between adjacent words) is $W(i, j) = \sum_{k=i}^{j-1} w_k + (j - 1 - i)$ (computable in $O(1)$ via prefix sums).
- The badness (or slack penalty) $\text{cost}(i, j)$ of a line spanning words $[i, j)$ is: $$\text{cost}(i, j) = \begin{cases} +\infty & \text{if } W(i, j) > L \\ 0 & \text{if } j = n \text{ (last line of paragraph is left-aligned)} \\ (L - W(i, j))^p & \text{otherwise } (p = 2 \text{ or } p = 3 \text{ in } \TeX) \end{cases}$$
Core Invariant — Suffix DP Recurrence & Sparse Active Breakpoint Window
Let $dp[i]$ be the minimum total badness to typeset the suffix of words $i \dots n-1$:
$$dp[i] = \min_{i < j \le n,\; W(i, j) \le L} \big(\text{cost}(i, j) + dp[j]\big), \qquad dp[n] = 0$$
Because every word has width $w_k \ge 1$ plus a space of width $1$, how many words $j - i$ can possibly fit on a single line of width $L$? At most $\lceil L / 2 \rceil$! As soon as $W(i, j) > L$, we break out of the inner $j$-loop immediately. Thus the time complexity is not $O(n^2)$, but $O(n \cdot W_{\text{max\_words\_per\_line}}) = O(n \cdot L)$—which is linear $O(n)$ for a fixed page width $L \approx 80$!
2. From $\TeX$ Paragraphs to Code Formatters (prettier, clang-format, rustfmt)
Modern source code formatters (clang-format, Wadler/Oppen pretty-printers in prettier and rustfmt) extend Knuth-Plass from flat word arrays to Abstract Syntax Trees (ASTs):
- Each token break has a syntactic penalty weight (breaking after a
,or;is cheap; breaking insidea + bis expensive) and an indentation level $I$. - Because indentation changes the remaining line budget $L - I$ for subsequent tokens, the state in
clang-formatis(token_index, column_offset, paren_stack_state)explored via Dijkstra / $A^*$ on the formatting DAG.
Hardware Reality — Concave Monge Property & $O(N)$ SMAWK / Convex Hull Acceleration
What if line width $L$ is huge (so $O(N \cdot L)$ is too slow)? Because the penalty function $f(x) = x^2$ or $x^3$ is convex, the transition matrix $C[i][j] = \text{cost}(i, j) + dp[j]$ satisfies the Quadrangle Inequality (Monge Property): optimal split points are monotonic ($\text{opt}[i] \le \text{opt}[i+1]$). Using Wilber's algorithm or Hirschberg-Larmore's Convex Hull / Monge deque, Knuth-Plass line breaking runs in strict $O(N)$ time regardless of $L$!
3. Complexity Matrix
Visualize how Hirschberg runs forward 2-row DP on the top half and reverse 2-row DP on the bottom half to locate the optimal midpoint crossing (M/2, k*) in linear memory.
Invariant & State
| Line-Breaking Algorithm | Time Complexity | Space Complexity | Global Optimality |
|---|---|---|---|
| Greedy Word Wrap (Browser / Notepad) | O(N) | O(1) | Suboptimal (Creates loose lines before long words) |
| Naive All-Pairs Suffix DP | O(N^2) | O(N) | Exact Global Optimum |
Knuth-Plass DP with Early W(i,j) > L Break |
O(N * (L / avg_w)) | O(N) | Exact Global Optimum (Linear for fixed $L$) |
| Monge / CHT Accelerated Knuth-Plass ($p=2$) | O(N) | O(N) | Exact Global Optimum for arbitrary $L$ |
4. Reference C++20 Implementation
#include <algorithm>
#include <cstdint>
#include <string>
#include <vector>
struct LineBreakPlan {
long long total_demerits;
// Pairs of [start_word_idx, end_word_idx_exclusive) for each formatted line
std::vector<std::pair<int, int>> lines;
};
// Knuth-Plass Optimal Paragraph Line Breaking with Cubic Badness Penalty
LineBreakPlan knuth_plass_line_break(const std::vector<int>& word_widths, int line_width) {
const int n = static_cast<int>(word_widths.size());
if (n == 0) return { 0, {} };
std::vector<int> pref(n + 1, 0);
for (int i = 0; i < n; ++i) pref[i + 1] = pref[i] + word_widths[i];
auto line_len = [&](int i, int j) -> int {
return (pref[j] - pref[i]) + (j - 1 - i);
};
constexpr long long INF = 1LL << 60;
std::vector<long long> dp(n + 1, INF);
std::vector<int> next_break(n + 1, n);
dp[n] = 0;
// Evaluate suffixes i = n-1 down to 0
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j <= n; ++j) {
int width = line_len(i, j);
if (width > line_width) {
// Only exception: a single word wider than line_width must still be placed on its own line
if (j == i + 1) {
dp[i] = dp[j];
next_break[i] = j;
}
break; // Monotonicity of width: no larger j can ever fit on this line!
}
long long slack = line_width - width;
// Last line (j == n) has 0 badness penalty in standard typography
long long badness = (j == n) ? 0LL : (slack * slack * slack);
if (badness + dp[j] < dp[i]) {
dp[i] = badness + dp[j];
next_break[i] = j;
}
}
}
// Reconstruct optimal line breaks from parent pointers next_break
LineBreakPlan plan{ dp[0], {} };
for (int cur = 0; cur < n; cur = next_break[cur]) {
plan.lines.emplace_back(cur, next_break[cur]);
}
return plan;
}Production Pitfall — Penalizing the Final Line ($j = n$) or Crashing on Overlong Words ($w_i > L$)
In real-world typesetting and code formatting, two edge cases must be handled explicitly: First, the final line of a paragraph ($j = n$) is ragged-right and should incur $0$ badness penalty for leftover slack (otherwise the solver will artificially pull words down from earlier lines just to pad the last line!). Second, if a single word or URL has $w_i > L$, breaking immediately when width > line_width at $j = i + 1$ leaves dp[i] = INF; a production formatter must allow single overfull tokens ($j = i + 1$) as a fallback.