Text Justification

Hard· simulation· greedy packing

Problem

Lay out a list of words into lines of exactly maxWidth characters. Pack as many words per line as fit, and spread extra spaces between words as evenly as possible, giving leftover spaces to the leftmost gaps. The last line, and any line with a single word, is left-aligned and padded with spaces on the right.

Examples

Input: words = ["Keep","code","clean","and","simple."], maxWidth = 12

Output: ["Keep code", "clean and", "simple. "]

Each full line spreads its spare spaces into the gap; the last line is left-aligned.

Constraints

• 1 <= words.length <= 300
• 1 <= words[i].length <= maxWidth <= 100

Hints & approach

Hint 1

First decide which words go on each line greedily.

Hint 2

For a normal line, divide the spare spaces by the number of gaps; the remainder goes to the leftmost gaps.

Hint 3

Treat the last line and single-word lines as special cases.

Approachtry the hints first

Walk the words, greedily adding each to the current line while the total letters plus one space per gap stays within maxWidth. When a line is complete, compute spare = maxWidth - letters and gaps = words - 1. If it is the last line or has one word, join with single spaces and pad on the right. Otherwise each gap gets spare / gaps spaces, and the first spare % gaps gaps get one more. Repeat until all words are placed.

Time O(total characters) · Space O(total characters)

← PreviousShortest Palindrome DoneBack to Strings