Word Wrap Problem

Hard

Problem

Given word lengths and a line width k, split the words into lines in their original order. Words on a line are separated by one space, and a line may not exceed k characters. The cost of a line is (unused spaces at its end)², and the last line costs nothing. Return the minimum total cost.

Example 1

Input:  lengths = [3, 2, 2, 5], k = 6
Output: 10

Lines: [3] (3 spare → 9), [2, 2] (1 spare → 1), [5] (last line → 0).

Also asked as: Word Wrap Problem · Word Wrap Problem [VERY IMP]

Test cases

Case 1

Input:    [3,2,2,5], 6
Expected: 10

Case 2

Input:    [3,2,2], 4
Expected: 5

Case 3

Input:    [1,1,1], 5
Expected: 0

Case 4

Input:    [4], 4
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. DP over line breaks

Time O(n²)Space O(n)

dp[i] = min total cost to arrange words i..n. Try every valid end word for the current line; cost = (trailing spaces)² summed over lines (last line free).

function wordWrap(lengths, width) {
const n = lengths.length;
const dp = Array(n + 1).fill(Infinity);
dp[n] = 0;
for (let i = n - 1; i >= 0; i--) {
let lineLen = -1;
for (let j = i; j < n; j++) {
lineLen += lengths[j] + 1;
if (lineLen > width) break;
const extra = j === n - 1 ? 0 : (width - lineLen) ** 2;
dp[i] = Math.min(dp[i], extra + dp[j + 1]);
}
}
return dp[0];
}