20 · String Parsing & Expression Evaluation
#68 Text Justification
frequently reported atAirbnbByteDance / TikTokUberAtlassianLinkedInGoogle
the problem
In plain words
Given a list of words and a width maxWidth, lay the words out as lines of exactly maxWidth characters. Put as many words on each line as fit, with at least one space between neighbours. Spread each line's spare spaces over its gaps as evenly as possible; when they don't divide evenly, the gaps on the left get one more. A line holding a single word, and the last line, are left-justified instead: one space between words, then spaces up to the width.
in words = ["This","is","an","example","of","text","justification."], maxWidth = 16
out ["This is an","example of text","justification. "]
Line 2 has 3 spare spaces for 2 gaps: the left gap gets 2, the right gets 1.
in words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
out ["What must be","acknowledgment ","shall be "]
"acknowledgment" is alone on its line, so it is left-justified; so is the last line.
- 1 ≤ words.length ≤ 300
- 1 ≤ words[i].length ≤ 20, no spaces inside a word
- words[i].length ≤ maxWidth ≤ 100
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternGreedy choiceSimulation
where this runsWeb browsers' default line breaking has used this kind of greedy first-fit; TeX uses Knuth–Plass to look at the whole paragraph instead.
Two separate jobs. Choosing a line's words is greedy: take words while they fit. Spacing a full line is arithmetic: spaces / gaps each, and the first spaces % gaps gaps get one extra.
solutions
From brute force to optimal
Join the line's words with single spaces, then insert one more space into the gaps in turn, left to right, until the line is full.
- Pick the line's words greedily.
- Last line or one word: pad the end.
- Otherwise: insert a space at gap 0, 1, 2, … (round and round) until the length is maxWidth.
Up to W inserted spaces per line, and each StringBuilder.insert shifts up to W characters (L lines, W = maxWidth).
One line and the gap positions, besides the output.
class Solution { public List<String> fullJustify(String[] words, int maxWidth) { List<String> lines = new ArrayList<>(); int i = 0; while (i < words.length) { int j = i, length = words[i].length(); // greedy: words i..j fit on this line while (j + 1 < words.length && length + 1 + words[j + 1].length() <= maxWidth) { length += 1 + words[++j].length(); } StringBuilder line = new StringBuilder(String.join(" ", Arrays.copyOfRange(words, i, j + 1))); int gaps = j - i; if (j == words.length - 1 || gaps == 0) { while (line.length() < maxWidth) line.append(' '); // left-justify: pad the end } else { int[] at = new int[gaps]; // where each gap's spaces end for (int g = 0, pos = 0; g < gaps; g++) { pos += words[i + g].length(); at[g] = pos; pos++; } // Add one space at a time, gap by gap, left to right, round and round. for (int g = 0; line.length() < maxWidth; g = (g + 1) % gaps) { line.insert(at[g], ' '); // insert shifts everything after it for (int h = g + 1; h < gaps; h++) at[h]++; } } lines.add(line.toString()); i = j + 1; } return lines; }}Fill each line greedily, then compute every gap's width directly: base = spaces / gaps, and the first spaces % gaps gaps get base + 1.
- From word i, take word j while letters + words[j].length() + (j − i) ≤ maxWidth.
- Last line or one word: join with single spaces, pad the end.
- Else spaces = maxWidth − letters; base = spaces / gaps; extra = spaces % gaps.
- Append each word, then base (+1 for the first extra gaps) spaces. Next line starts at j.
Each word is tested once for fit and every output character is written once.
The builder for one line, besides the output list.
class Solution { public List<String> fullJustify(String[] words, int maxWidth) { List<String> lines = new ArrayList<>(); int i = 0; while (i < words.length) { int j = i + 1, letters = words[i].length(); // Take the next word while the letters plus one space per gap still fit. while (j < words.length && letters + words[j].length() + (j - i) <= maxWidth) { letters += words[j].length(); j++; } int gaps = j - i - 1; StringBuilder line = new StringBuilder(maxWidth); if (j == words.length || gaps == 0) { // last line, or one word: left-justify for (int k = i; k < j; k++) { if (k > i) line.append(' '); line.append(words[k]); } line.append(" ".repeat(maxWidth - line.length())); } else { int spaces = maxWidth - letters; int base = spaces / gaps, extra = spaces % gaps; // the first `extra` gaps get one more for (int k = i; k < j; k++) { line.append(words[k]); if (k < j - 1) line.append(" ".repeat(base + (k - i < extra ? 1 : 0))); } } lines.add(line.toString()); i = j; } return lines; }}Dry run
in the room
How to say it in the interview
talk track
- Separate the two jobs out loud: pick the words, then space them.
- Write the fit test: letters + words[j].length() + (j − i) ≤ maxWidth.
- Do the arithmetic on example 1's second line: 3 spaces, 2 gaps → 2 and 1.
- List the special cases before coding: the last line, and lines with one word.
traps
- Forgetting that one-word lines are left-justified — with 0 gaps, spaces / gaps divides by zero.
- Giving the extra spaces to the right-hand gaps; the left ones get them.
- Off-by-one in the fit test: k words need k − 1 spaces.
what they ask next
Follow-ups
Make the paragraph look as even as possible, not just greedy?
That's Knuth–Plass: dynamic programming over all break points, minimising a total cost such as the sum of squared leftover spaces per line. TeX does this.
Center each line instead?
Same greedy lines with single spaces; put (maxWidth − length) / 2 spaces on the left and the rest on the right.
before you submit
Edge cases to test
- A word exactly maxWidth long fills its line alone.
- The last line keeps single spaces even when it holds many words.
- Spaces that divide evenly: no gap gets an extra one.
practise next
Similar problems
- #151Reverse Words in a StringMediumin Parsing
- #763Partition LabelsMediumin Greedy
- #271Encode and Decode StringsMediumin ParsingLeetCode Premium