Word Wrap Problem

The problem, simply

You get the lengths of n words, in order, and a line width k. Put the words on lines, keeping their order. Words on the same line need one space between them, and a line may not be longer than k. Every word fits on a line by itself.

A line with e empty spaces left at its end costs e x e. The last line is free, because a short last line looks fine. Give back the smallest total cost.

A story to remember it

Picture it

Filling each line as much as possible looks tidier at the top but costs more:

Examples

Way 1: the simple way

f(i) is the best cost for the words from i to the end.

1. If no words are left, the cost is 0.
2. Try putting words i to j on the first line, for j = i, i + 1, ... as long as they fit.
3. That line costs extra x extra, or 0 if it holds the last word. Add f(j + 1).
4. Keep the smallest.

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

    // best cost for words i..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 gap
        for (int j = i; j < n; j++) {
            len += nums[j] + 1;                      // the word plus one gap
            if (len > k) break;                      // does not fit
            int extra = k - len;
            int lineCost = (j == n - 1) ? 0 : extra * extra;   // last line is free
            answer = Math.min(answer, lineCost + best(nums, k, j + 1));
        }
        return answer;
    }
}

How long it takes: every place between two words is either a line break or not, so up to O(2^n) plans. Extra room: the call chain, O(n).

Way 2: the clever way

There are only n different questions f(0), f(1), ..., f(n - 1). Answer them from the back, in a row cost[0..n], so each one only reads answers that are already there.

1. cost[n] = 0.
2. For i from n - 1 down to 0: grow the first line one word at a time. For each line i..j that fits, try lineCost + cost[j + 1].
3. cost[i] is the smallest try. Return cost[0].

class Solution {
    public int solveWordWrap(int[] nums, int k) {
        int n = nums.length;
        int[] cost = new int[n + 1];                 // cost[n] = 0: no words left
        for (int i = n - 1; i >= 0; i--) {
            cost[i] = Integer.MAX_VALUE;
            int len = -1;
            for (int j = i; j < n; j++) {
                len += nums[j] + 1;                  // add word j and a gap
                if (len > k) break;                  // line too long
                int extra = k - len;
                int lineCost = (j == n - 1) ? 0 : extra * extra;
                cost[i] = Math.min(cost[i], lineCost + cost[j + 1]);
            }
        }
        return cost[0];
    }
}

How long it takes: for each start i, the line grows over at most n words, O(n^2) (and only O(n * k) when lines hold few words). Extra room: the row, O(n).

Watch out for

• The last line is free. Forgetting this makes the answer too big. But only the line that holds the last word is free.
• Count the gaps. A line with words i..j has j - i gaps of one space. Starting len at -1 and adding word + 1 handles that neatly.
• Read the cost rule. This version (GeeksforGeeks) uses squares. Some textbooks use cubes. The method is the same, only lineCost changes.
• extra * extra can overflow for very wide pages with cubes. Use long if needed.

What interviewers ask next

• Print where the lines break. Store brk[i] = j + 1 for the best choice, then follow brk from 0.
• Why squares and not plain extra spaces? With plain sums, one hole of 4 costs the same as two holes of 2. Squaring makes the big hole cost 16 and the two small ones only 8, so lines come out more even.
• Can it be faster than O(n^2)? Yes, for square costs there are clever O(n log n) methods (Hirschberg and Larmore), but O(n^2) is what interviewers expect.
• Text justification (LeetCode 68) is a different question: it uses greedy packing and then spreads spaces inside each line.

Remember this

Grown-up words: the empty boxes are slack, the messy points are a squared penalty, breaking lines in order is the word wrap or line breaking problem, and solving from the back with a row is 1D dynamic programming over suffixes.