Text Justification (Hard)

Good morning! Here's our prompt for today.

You may see this problem at Nvidia, Twilio, Procore, Toast, Fastly, Digitalocean, 3m, Proofpoint, Zoominfo, Sonos, and Expedia.

Can you justify input text represented by an array of words so it looks pretty when printed and the whitespaces are balanced?

For example, in the above image, we have an input array of ["wow", "so", "cool", "is", "algodaily!"]. This is a list of words we need to properly arrange, with the ideal number of spaces in between, to balance out the layout.

Constraints

• The string can be empty, in which case return an empty string
• The string will consist of only lowercase alphabets
• Expected time complexity : O(n^2)
• Expected space complexity : O(n)

Text Justification

An obvious solution for text justification is to fit as many words as possible in all the lines. So with ["wow", "so", "cool", "is", "algodaily!"], and an example layout of 10 spaces: we'd place all 3 words: "wow", "so", and "cool", into one single line with no spaces. However, the text would not look pretty if such a naïve scheme is used for justifying text.

A better idea is to evenly distribute spaces on all lines of text for a more aesthetically looking display. This is obvious from the figure shown above, where arrangement 2 is more balanced than arrangement 1.