68. Text Justification
You are given an array of words words and a line width max_width. Typeset the words the way a justified newspaper column would.
Pack greedily: keep appending words to the current line as long as the line — counting a single space between neighbors — still fits within max_width characters. When the next word can't fit, the line is finished and a new one begins.
Every finished line must then be stretched to exactly max_width characters:
- A line that is not the last line and holds two or more words is fully justified: the leftover spaces are spread across the gaps between words as evenly as possible, and when they don't divide evenly the leftmost gaps receive one extra space each.
- A line holding a single word, and the final line, are left-justified instead: words separated by one space, then padded with spaces on the right up to
max_width.
Return the finished lines, in order, as a list of strings.
Example 1:
Input: words = ["the", "quick", "brown", "fox", "jumps", "over", "a", "lazy", "dog"], max_width = 12
Output: ["the quick", "brown fox", "jumps over a", "lazy dog "]
Explanation: Rows 1–2 each hold two words, so all leftover spaces pour into the single gap. Row 3 fits three words perfectly with one space per gap. The final row is left-justified and padded on the right.
Example 2:
Input: words = ["code", "every", "single", "day", "now"], max_width = 10
Output: ["code every", "single day", "now "]
Explanation: "code every" and "single day" already measure exactly 10 with single spaces, so no extra padding lands in their gaps. "now" is the last line: left-justified with 7 trailing spaces.
Constraints:
- 1 ≤ words.length ≤ 300
- 1 ≤ words[i].length ≤ 20
- words[i] consists of printable non-space characters
- words[i].length ≤ max_width ≤ 100
Hints:
Split the job in two: decide which words share each line (pure greedy — a word joins the current line if current width + 1 + its length stays within max_width), then, separately, stretch each finished line.
For a fully justified line with `g` gaps and `s` total spaces to place, give every gap `s // g` spaces and hand one extra to each of the first `s % g` gaps — that's exactly 'as even as possible, left gaps first'.
The exceptions are what make this Hard: a line with a single word has no gaps to stretch, and the last line must never be stretched. Both are left-justified and right-padded. Handle them before the even-distribution math.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: words = ["the", "quick", "brown", "fox", "jumps", "over", "a", "lazy", "dog"], max_width = 12
Expected output: ["the quick", "brown fox", "jumps over a", "lazy dog "]