Text Justification Solution for Google
Company: Google · Difficulty: Hard · Topics: String, Array, Simulation
Problem Statement
Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth 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, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left-justified, and no extra space is inserted between words.
Examples
Example 1:
Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Output: [
"This is an",
"example of text",
"justification. "
]
Explanation:
- Line 1: "This is an" (16 characters)
- Line 2: "example of text" (16 characters)
- Line 3: "justification. " (16 characters, left-justified)
Example 2:
Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
Output: [
"What must be",
"acknowledgment ",
"shall be "
]
Explanation:
- Line 1: "What must be" (16 characters)
- Line 2: "acknowledgment " (16 characters, left-justified)
- Line 3: "shall be " (16 characters, left-justified)
Example 3:
Input: words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"], maxWidth = 20
Output: [
"Science is what we",
"understand well",
"enough to explain to",
"a computer. Art is",
"everything else we",
"do "
]
Intuition
The key insight is to process words line by line, calculating how many words can fit in each line while maintaining the maxWidth constraint. For each line, we need to distribute spaces evenly between words, with extra spaces going to the left slots.
Approach
Approach 1: Greedy Line Packing (Optimal)
1. Process words one by one, building lines
2. For each line, calculate how many words can fit
3. Distribute spaces evenly between words
4. Handle the last line specially (left-justified)
Approach 2: Dynamic Programming
1. Use DP to find optimal line breaks
2. Calculate minimum raggedness
3. Reconstruct the justified text
Approach 3: Brute Force
1. Try all possible line break combinations
2. Calculate space distribution for each
3. Choose the best arrangement
Dry Run
Let's trace through Example 1: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Line 1: "This is an"
- Words: ["This", "is", "an"] (3 words)
- Total word length: 3 + 2 + 2 = 7
- Available spaces: 16 - 7 = 9
- Spaces between words: 9 / (3-1) = 4.5 → 5, 4
- Result: "This is an"
Line 2: "example of text"
- Words: ["example", "of", "text"] (3 words)
- Total word length: 7 + 2 + 4 = 13
- Available spaces: 16 - 13 = 3
- Spaces between words: 3 / (3-1) = 1.5 → 2, 1
- Result: "example of text"
Line 3: "justification."
- Words: ["justification."] (1 word)
- Last line: left-justified
- Result: "justification. "
Solution
Note: This solution provides multiple approaches to solve the problem. Choose the one that best fits your understanding and requirements.
Key Insights:
1. Greedy Packing: Always try to fit as many words as possible in each line
2. Space Distribution: Distribute spaces evenly, with extra spaces on the left
3. Last Line: Always left-justified with single spaces between words
Edge Cases:
- Single word per line: no spaces between words
- Last line: left-justified regardless of space distribution
- Words that exceed maxWidth: should not occur per problem constraints
Time Complexity
- Greedy Approach: O(n) where n is total number of words
- Dynamic Programming: O(n²)
- Brute Force: O(2^n)
Space Complexity
- Greedy Approach: O(n) for output
- Dynamic Programming: O(n²)
- Brute Force: O(n)