Word Wrap Problem
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
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];}