codejump
HardPro challengePythonJavaScriptTypeScript

Strings — Text Justification

AlgorithmsStringsSimulationGreedy

solve(words, maxWidth) — format words into lines of exactly maxWidth characters,
fully justified. Return the array of lines.

  • Pack words greedily: put as many words on a line as fit, with at least one space between

consecutive words.

  • Pad the extra spaces so the line is maxWidth long. Spaces between words are distributed

as evenly as possible; if they do not divide evenly, the leftmost gaps get one more.

  • A line with a single word, and the last line, are left-justified: words separated by a

single space, then padded with spaces on the right.

  • Every word is at most maxWidth long.

Example

words = ["This","is","an","example","of","text","justification."], maxWidth = 16
→ [
    "This    is    an",
    "example  of text",
    "justification.  "
  ]

For each line, find how many words fit, then count the total spaces to distribute:
maxWidth - sum of the word lengths, spread over words - 1 gaps with
floor(total / gaps) each and total % gaps extra on the left.

Sample tests

Test #1Classic example
Input: [["This","is","an","example","of","text","justification."],16]
Output: ["This is an","example of text","justification. "]
Test #2Single-word line and last line
Input: [["What","must","be","acknowledgment","shall","be"],16]
Output: ["What must be","acknowledgment ","shall be "]
Test #3Uneven space distribution
Input: [["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"],20]
Output: ["Science is what we","understand well","enough to explain to","a computer. Art is","everything else we","do "]
← All challenges