Text Justification

Examples:

Input: ["This", "is", "an", "example", "of", "text", "justification."]

Output: ["This is an", "example of text", "justification. "]

Explanation: The first line has 13 characters (This + is + an), so we add 4 spaces to the right. The second line has 15 characters (example + of + text), so we add 2 spaces to the right. The last line has 15 characters (justification), so we add 7 spaces to the right.

Solutions

Greedy Algorithm

Time: O(n*m)Space: O(n*m)

The solution uses a greedy algorithm to justify the text. It iterates over the words and adds them to the current line. If the current line exceeds the maximum width, it justifies the current line and adds it to the result. The last line is left-justified.

function fullJustify(words, maxWidth) {
  let result = [],
    currentLine = [],
    currentWidth = 0;

  for (let word of words) {
    if (currentWidth + word.length + currentLine.length > maxWidth) {
      let spaces = maxWidth - currentWidth;

      let gaps = currentLine.length - 1;

      if (gaps === 0) {
        result.push(currentLine[0] + ' '.repeat(spaces));
      } else {
        let spaceEachGap = Math.floor(spaces / gaps);

        let extraSpaces = spaces % gaps;

        let line = '';

        for (let i = 0; i < currentLine.length; i++) {
          line += currentLine[i];

          if (i < currentLine.length - 1) {
            line += ' '.repeat(spaceEachGap + (i < extraSpaces ? 1 : 0));
          }
        }

        result.push(line);
      }

      currentLine = [word];

      currentWidth = word.length;
    } else {
      currentLine.push(word);

      currentWidth += word.length;
    }
  }

  let lastLine = currentLine.join(' ');

  lastLine += ' '.repeat(maxWidth - lastLine.length);

  result.push(lastLine);

  return result;
}

Constraints:

Examples:

Solutions

Greedy Algorithm

Follow-up: