Word Wrap Problem

The problem, simply

You get the lengths of n words, in order, and a line width k. Words on the same line are separated by one space. You must keep the words in order and choose where each line ends. Every word fits on a line by itself.

Each line except the last one leaves some empty spots at its end, the extra spaces. The cost of a line is (extra spaces) times (extra spaces). The last line is free. Give back the smallest total cost.

Squaring is the point. Two lines with 2 empty spots each cost 4 + 4 = 8, but one line with 4 and one with 0 cost 16. Squares punish one big ugly gap more than a few small ones.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every choice. For the first word, try putting 1 word on the first line, then 2 words, and so on, while they fit. For each choice, solve the rest the same way and keep the cheapest.

1. If no words are left, the cost is 0.
2. Grow the first line one word at a time. The line length is the word lengths plus one space between each pair.
3. Stop when the line is longer than k.
4. The line costs (k - length)^2, or 0 if it holds the last word.
5. Add the best cost of the rest, and keep the smallest total.

class Solution {
    public int solveWordWrap(int[] nums, int k) {
        return best(nums, k, 0);
    }

    // least total cost to place words i, i+1, ..., n-1
    private int best(int[] nums, int k, int i) {
        int n = nums.length;
        if (i == n) return 0;
        int answer = Integer.MAX_VALUE;
        int len = -1;                               // so the first word adds no space
        for (int j = i; j < n; j++) {
            len += nums[j] + 1;                     // word j joins the line
            if (len > k) break;                     // too wide
            int extra = k - len;
            int cost = (j == n - 1) ? 0 : extra * extra;   // the last line is free
            answer = Math.min(answer, cost + best(nums, k, j + 1));
        }
        return answer;
    }
}

How long it takes: every gap between two words is either a line break or not, so there are up to 2^(n - 1) layouts, and the same "rest" is solved many times. O(2^n). Extra room: the call stack, O(n).

Way 2: the clever way

The rest after word j always has the same best answer, no matter how you got there. So compute it once, from the last word to the first.

1. dp[i] = least cost to place words i to n - 1. Set dp[n] = 0.
2. For i from n - 1 down to 0, grow a line that starts at word i, one word j at a time, while it fits.
3. Each choice costs lineCost + dp[j + 1]. Keep the smallest in dp[i].
4. The answer is dp[0].

class Solution {
    public int solveWordWrap(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n + 1];       // dp[i]: least cost for words i..n-1
        dp[n] = 0;                       // no words left
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = Integer.MAX_VALUE;
            int len = -1;
            for (int j = i; j < n; j++) {
                len += nums[j] + 1;      // put word j on the line that starts at i
                if (len > k) break;      // too wide: stop growing
                int extra = k - len;
                int cost = (j == n - 1) ? 0 : extra * extra;
                dp[i] = Math.min(dp[i], cost + dp[j + 1]);
            }
        }
        return dp[0];
    }
}

How long it takes: for each word, the inner loop runs once per word on its line, and a line holds at most about k / 2 words, so O(n * k), and never more than O(n^2). Extra room: the dp array, O(n).

Watch out for

• Forgetting the free last line. The line that holds word n - 1 costs 0, whatever its gaps.
• Counting the spaces wrong. m words on a line use m - 1 spaces. Starting len at -1 and adding length + 1 for each word does this neatly.
• Overflow. With long lines and many words, squares add up fast. Use long if the limits are big.
• Not the same problem as LeetCode 68, Text Justification. There the lines are filled greedily and the spaces are spread inside each line. Ask which one is meant.

What interviewers ask next

• Print the lines too. Store next[i] = j + 1 for the best choice, then follow next from 0.
• Cost with cubes instead of squares, or a penalty for breaking certain words? Same dp, only the line cost changes.
• Faster for huge texts? Real typesetting (Knuth and Plass, used in TeX) uses the same idea with smarter pruning. Because a squared cost grows like a bowl, a known trick with a deque and binary search brings it to O(n log n). Interviews rarely go that far.
• Why is it fine to go right to left? The cost of the rest of the words does not depend on how the earlier lines were made.

Remember this

Grown-up words: the sticky notes are a 1D DP table, planning from the back is a suffix recurrence, filling each box full is the greedy approach, and the squared gaps are a convex cost function.