Objective Function

For any optimization problem, we have to define the objective function or the fitness function. This is defined as a function that "attempts to maximize profits or minimize losses based on a set of constraints and the relationship between one or more decision variables".

In the case of text justification, the optimization function is dependent upon the number of white spaces being added to each line.

The more the spaces, the poorer "the performance". Hence, we want to minimize the total number of extra spaces that occur in a line.

Based on this idea, the objective function is defined as such: we have a higher value if there are more spaces between words. The goal is to find an arrangement of text that minimizes the objective function.

Let's consider what pieces of information we need. We'll use the following notations in this tutorial. Feel free to refer back to this if you ever get lost.

1n       = total number of input words
2L       = total number of lines in our solution
3word[i] = word at index i
4f(i,j)  = cost function for a line that starts at word[i] and ends at word[j]
5cost    = overall cost of the solution

Based on the above notations, let's define width(i, j)-- our objective function-- as:

By using width(i, j) to measure spacing, we have defined the cost function $f(i,j)$ associated with a line that starts with word word[i] and ends at word word[j]. Note that this function is zero for the last line, as we need not add any extra space there.

The figure below shows the example of computing $f(i,j)$ and its corresponding cost for two different arrangements. Our aim is to choose those lines for which the above cost function is a minimum. Hence, we have to find, the indices of the words that lie at the line boundaries, i.e.,:

$\text{find:}{k}_1,k_2,\dots ,k_{L-1}$

Armed with the above concepts, we are now ready to define our dynamic programming problem.

Formulation of Dynamic Programming

The problem of text justification can be solved using dynamic programming as it can be divided into sub-problems, each having a recursive sub-structure. We'll define an overall cost function DP[i], associated with each word as given by:

1DP[i] = minimum cost of justifying text that starts with word[i]

DP[i] can be defined in terms of the function $f(i,j)$, that we defined above:

1DP[n] = 0
2DP[i] = min(f(i,j)+DP[j+1]) where min is over j=(i+1)...(n-1)
3        and i=0..(n-1)

This gives us a convenient and easy method of finding the word boundaries for each line. Hence we can define split[i], which stores the index of the word that ends the line starting with word[i], in an optimal arrangement.

1split[i] = argmin(f(i,j)+DP[j+1]) where argmin is over j=(i+1)...(n-1)
2            and i=0..(n-1)

The final solution's overall cost is DP[0]. Figure below shows DP array for all words of our input word array, with an optimal minimum cost of 189.

One Pager Cheat Sheet

• We can achieve a more balanced text layout by evenly distributing spaces between all words on each line, while fitting as many words as possible, in O(n^2) time, using O(n) space complexity.
• Our goal is to minimize the cost of text justification by finding the arrangement of words with the least amount of extra spaces between them.
• Dynamic programming can be used to divide a text justification problem into sub-problems, each with a recursive sub-structure, and an overall cost function can be found using f(i,j) and DP[i] to determine the optimal word boundary for each line with split[i].
• The DP and split arrays can be computed using an optimized for loop pseudo-code algorithm.
• We can determine the lines of text in our solution by tracking the index of the last word in each line using a list called lineEnd and then justifying the text by inserting the right amount of spaces between words.
• The time complexity is O(n$^2$) and the **space complexity** isO(n)` for the dynamic programming solution of the text justification problem.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require('assert');

​

function textJustification(words, maxWidth) {

  const res = [[]];

  res[0].letters = 0;

  for (let word of words) {

    let row = res[res.length - 1];

    if (row.length && row.letters + row.length + word.length > maxWidth) {

      res.push([]);

      row = res[res.length - 1];

      row.letters = 0;

    }

    row.push(word);

    row.letters += word.length;

  }

  for (let r = 0; r < res.length; r++) {

    let row = res[r];

    if (row.length === 1 || r === res.length - 1) {

      res[r] =

        row.join(' ') + ' '.repeat(maxWidth - row.letters - row.length + 1);

      continue;

    }

    let line = row[0];

    let spaces = maxWidth - row.letters;

    let minSpaces = ' '.repeat(Math.floor(spaces / (row.length - 1)));

    let addSpace = spaces % (row.length - 1);

    for (let w = 1; w < row.length; w++) {

      line += minSpaces + (w <= addSpace ? ' ' : '') + row[w];

    }

    res[r] = line;

  }

  return res.join('\n');

You're doing a wonderful job. Keep going!

If you had any problems with this tutorial, check out the main forum thread here.