#68

Hard

LeetCode Problem Workspace

Text Justification

Text Justification requires packing words into lines to match a specified width, ensuring even distribution of spaces.

Problem Statement

Given an array of words and a maximum width (maxWidth), the task is to justify the text. Each line must contain as many words as possible, and the total length of the words plus spaces must exactly match the given maxWidth. If extra spaces are needed, distribute them as evenly as possible between words. If the spaces cannot be evenly distributed, the leftmost spaces should be placed first.

The last line should be left-justified, meaning it is filled with words but without extra space between them. If the line contains only one word, it should be left-justified with any remaining space filled at the end of the line. Handle the edge cases where lines may have one or no words.

Examples

Example 1

Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16

Output: [ "This is an", "example of text", "justification. " ]

Example details omitted.

Example 2

Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16

Output: [ "What must be", "acknowledgment ", "shall be " ]

Note that the last line is "shall be " instead of "shall be", because the last line must be left-justified instead of fully-justified. Note that the second line is also left-justified because it contains only one word.

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 " ]

Example details omitted.

Constraints

1 <= words.length <= 300
1 <= words[i].length <= 20
words[i] consists of only English letters and symbols.
1 <= maxWidth <= 100
words[i].length <= maxWidth

Solution Approach

Greedy Approach

The problem follows a greedy approach where you try to fit as many words as possible in each line. The greedy method ensures that each line gets as many words as it can without exceeding maxWidth.

Space Distribution

After packing the words, spaces must be distributed evenly between the words. If the remaining spaces are not divisible by the number of spaces between words, place the extra spaces from left to right.

Left Justification for the Last Line

The last line of text should always be left-justified. No extra spaces between words, and any remaining space should be added at the end.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the final approach. Typically, it involves iterating over the words and distributing spaces, leading to an O(n) time complexity where n is the number of words. The space complexity depends on the storage of the formatted output, which is O(n) as well.

What Interviewers Usually Probe

Able to explain space distribution in detail.
Can implement a greedy approach effectively.
Demonstrates understanding of left justification and its edge cases.

Common Pitfalls or Variants

Common pitfalls

Incorrectly distributing spaces when the number of spaces doesn't divide evenly.
Forgetting that the last line should be left-justified.
Overcomplicating the space distribution by adding extra checks.

Follow-up variants

Handling very large maxWidth values.
Handling words with different lengths efficiently.
Implementing an alternative approach that minimizes space usage while keeping time complexity optimal.

FAQ

How do I approach the Text Justification problem?

Start by packing words into lines using a greedy approach, ensuring the total line width does not exceed maxWidth. Then, distribute spaces evenly between the words, with extra spaces placed on the left. Finally, make sure the last line is left-justified.

What happens if the spaces can't be evenly distributed?

If the spaces cannot be evenly distributed, the extra spaces are added from left to right, meaning the leftmost spaces will get more space than the rightmost.

Why is the last line always left-justified?

The last line is left-justified to ensure that no extra space is added between words, and the remaining space is filled at the end of the line.

How do I handle edge cases like a single word on a line?

If there's only one word on the line, the line will be left-justified, and the remaining spaces will be added at the end of the line.

What is the time complexity of solving Text Justification?

The time complexity is typically O(n), where n is the number of words. This involves iterating over the words and distributing spaces in each line.

terminal

Solution

Solution 1: Simulation

We can simulate the process according to the problem's requirements. Note that if it is the last line, or if there is only one word in the line, then we should align to the left. Otherwise, we should distribute the spaces evenly.

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        ans = []
        i, n = 0, len(words)
        while i < n:
            t = []
            cnt = len(words[i])
            t.append(words[i])
            i += 1
            while i < n and cnt + 1 + len(words[i]) <= maxWidth:
                cnt += 1 + len(words[i])
                t.append(words[i])
                i += 1
            if i == n or len(t) == 1:
                left = ' '.join(t)
                right = ' ' * (maxWidth - len(left))
                ans.append(left + right)
                continue
            space_width = maxWidth - (cnt - len(t) + 1)
            w, m = divmod(space_width, len(t) - 1)
            row = []
            for j, s in enumerate(t[:-1]):
                row.append(s)
                row.append(' ' * (w + (1 if j < m else 0)))
            row.append(t[-1])
            ans.append(''.join(row))
        return ans

Continue Practicing

#67 add binary #59 spiral matrix ii #79 word search