# Word Wrap

Given a sequence of n words and the limit of the length of each line M, let the cost of putting k words with total m characters in a line be $(M - m - k + 1)^3$, design an O(n lg n) time algorithm to find the optimal way to break the sequence of words into lines with minimum cost.

Solution:

The solution is based on dynamic programming. Let p[i] be the total length for the first i words. Let c[i][j] be the cost of putting the i-th word to j-th word in the same line. By using the prefix sum of the length, each element of c[i][j] can be computed in constant time. Let F[i] be the optimal objective value for the subproblem containing the first i words. We get a recurrence relation F[j] = $\min_{1 \leq i < j}$ F[i] + c[i][j]. By using the recurrence relation, we get an O($n^2$) time algorithm.

In order to speed up, note that c[i][j] satisfies quadrangle inequality, that is c[i][k] + c[j][l] ≤ c[i][l] + c[j][k] for all i ≤ j ≤ k ≤ l. Furthermore, let d[i][j] = F[i] + c[i][j], the problem becomes finding the minimum for each column of matrix d. Note that the matrix d also satisfies quadrangle inequality. We will use a queue = ($i_1, h_i$), …, ($i_k, h_k$) to maintain the candidates, where $i_1 \leq i_2 \dots \leq i_k$ and ($i_1, h_1$) is in the front of the queue. When processing to the j-th column, one element ($i_r, h_r$) in the queue means that in the submatrix d[1..j-2][j..n], row $i_r$ is the column minimum for columns $h_r$ to $h_{r+1} - 1$. Initially, the queue only contains (1, 1). When consider the column j, if d[j-1][n] is smaller then d[$i_k$][n], then we need to dequeue until the d[$i_r$][$h_r$] < d[j-1][$h_r$], where $i_r$ is the rear of the queue. Then, we find the smallest h > $h_r$, such that d[$i_r$][h] < d[j-1][h] and enqueue (j-1, h+1). Finding such h needs O(lg n) time by using binary search. Since each index can be enqueue and dequeue once, the total complexity is O(n lg n).

Note: This problem can be solved in linear time by using slope optimization.

Reference: Zvi Galil and Kunsoo Park, “Dynamic programming with convexity, concavity and sparsity,” Theoretical Computer Science Volume 92, Issue 1, 6 January 1992, Pages 49–76.

Geeksforgeeks