All problems

Text Justification

Hard · strings

You are given a list of words and a line width max_width. Lay the words out in lines of exactly max_width characters, like the lines of a justified newspaper column.

Build the lines with these rules:

  1. Fill greedily. Put as many consecutive words on a line as will fit, with at least one space between neighbouring words. The words keep their order and are never split.
  2. Spread the spaces. In every line except the last, add spaces between the words until the line is exactly max_width characters long. The gaps should be as equal as possible. If the spaces cannot be shared equally, the gaps further to the left get one extra space each, before any gap further to the right does.
  3. A lone word. A line (other than the last) that holds only one word has the word at the left, followed by enough spaces to reach max_width.
  4. The last line is left-aligned: one space between neighbouring words, then spaces after the last word to reach max_width.

Return the lines as a list of strings. Every string in it has length max_width.

Examples

Example 1

Input: words = ["ab", "c", "d", "efg"], max_width = 9

Output: ["ab c d", "efg "]

The first line holds ab, c and d. Five spaces are shared by two gaps: 3 on the left gap and 2 on the right one. efg is alone on the last line and is padded on the right.

Example 2

Input: words = ["go", "to", "bed", "now", "please"], max_width = 8

Output: ["go to", "bed now", "please "]

A line with two words puts all the spare spaces in the single gap. The last line is padded on the right.

Example 3

Input: words = ["abcde", "fghij", "k"], max_width = 6

Output: ["abcde ", "fghij ", "k "]

A line that holds a single word is padded on the right, even when it is not the last line.

Constraints