Algorithms & Data Structureshard

Max Width

Given an array of words and a max_width parameter, write a function justify to format the text such that each line has exactly max_width characters. Pad extra spaces " " when necessary so that each line has exactly max_width characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, place excess spaces on the right-hand side of each line.

Note: you may assume that there is no word in words that is longer than max_width.

Example:

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

justify(words, max_width)
=> [
  "This    is    an",
  "example  of text",
  "justification.  "
]

Hints

Hint 1

Greedy: keep adding words to the current line while they still fit with single spaces between them, then justify the finished line.

Hint 2

For a line with g gaps and s spaces to place, every gap gets floor(s / g), and the leftmost s mod g gaps get one extra — that reproduces "example of text" from the example.

Hints

Asked at