LeetCode 68: Text Justification Solution in Python Explained

Problem Statement

LeetCode 68, Text Justification, is a hard-level problem where you’re given an array of strings words and an integer maxWidth. Your task is to format the text such that each line has exactly maxWidth characters, fully justified (left and right), except for the last line, which is left-justified. Extra spaces are distributed as evenly as possible between words, with additional spaces added to the left if uneven. Return the formatted lines as a list of strings.

Constraints

  • 1 <= words.length <= 300: Number of words is between 1 and 300.
  • 1 <= words[i].length <= 20: Each word’s length is between 1 and 20.
  • words[i] consists of English letters and symbols.
  • 1 <= maxWidth <= 100: Maximum width is between 1 and 100.
  • words[i].length <= maxWidth: Each word fits within maxWidth.

Example

Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Output: [
   "This    is    an",
   "example  of text",
   "justification.  "
]
Explanation:
<ul>
<li>"This    is    an" (4+2+2+2=10 chars + 6 spaces = 16)</li>
<li>"example  of text" (7+2+4=13 chars + 3 spaces = 16)</li>
<li>"justification.  " (14 chars + 2 spaces = 16, left-justified)</li>
</ul>

Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
Output: [
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]
Explanation: Multiple valid outputs exist; last line is left-justified.

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

Understanding the Problem

How do you solve LeetCode 68: Text Justification in Python? For words = ["This", "is", "an", "example", "of", "text", "justification."] and maxWidth = 16, format the text into lines of exactly 16 characters, fully justified except for the last line, which is left-justified. We need to pack words into lines, distribute spaces, and handle special cases. We’ll explore two approaches: a Greedy Line Packing Solution (optimal and primary) and an Alternative with Word Grouping (similar but structured differently). The greedy method runs in O(n) time with O(maxWidth) space.

Solution 1: Greedy Line Packing Approach (Primary)

Explanation

Greedily pack words into lines until adding the next word exceeds maxWidth. For each line, calculate the number of spaces needed and distribute them evenly between words, with extra spaces on the left. The last line is left-justified with spaces appended to reach maxWidth.

Here’s a flow for ["This", "is", "an"], maxWidth = 16:

Line: "This" (4) + "is" (2) + "an" (2) = 8 chars
Spaces: 16-8 = 8, 2 gaps, 4 spaces each
Result: "This    is    an"
  1. Pack Words.
  • Add words until exceeding maxWidth.
  1. Justify Line.
  • Distribute spaces evenly, special case for last line.
  1. Repeat Until Done.
  • Process all words into lines.
  1. Return Result.

Step-by-Step Example

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

We need ["This is an", "example of text", "justification. "].

  • Goal: Justify text to 16 characters per line.
  • Result for Reference: ["This is an", "example of text", "justification. "].
  • Start: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16, result = [], i = 0.
  • Step 1: First line.
    • i = 0, "This" (4), fits.
    • i = 1, "is" (2), total = 6 + 1 = 7, fits.
    • i = 2, "an" (2), total = 9 + 1 = 10, fits.
    • i = 3, "example" (7), total = 17 + 1 = 18 > 16, stop.
    • Words: ["This", "is", "an"], chars = 8, gaps = 2, spaces = 8.
    • Spaces per gap = 4, line = "This is an".
    • result = ["This is an"], i = 3.
  • Step 2: Second line.
    • i = 3, "example" (7), fits.
    • i = 4, "of" (2), total = 9 + 1 = 10, fits.
    • i = 5, "text" (4), total = 14 + 1 = 15, fits.
    • i = 6, "justification." (14), total = 29 > 16, stop.
    • Words: ["example", "of", "text"], chars = 13, gaps = 2, spaces = 3.
    • Spaces per gap = 1, extra = 1, line = "example of text".
    • result = ["This is an", "example of text"], i = 6.
  • Step 3: Last line.
    • i = 6, "justification." (14), fits, i = 7 (end).
    • Left-justify: "justification. " (14 + 2 spaces).
    • result = ["This is an", "example of text", "justification. "].
  • Finish: Return result.

Example 2: words = ["What","must","be"], maxWidth = 16

We need ["What must be"].

  • Start: i = 0.
  • Step 1: Only line.
    • "What" (4), "must" (4), "be" (2), total = 10 + 2 = 12 < 16.
    • i = 3 (end), chars = 10, gaps = 2, spaces = 6.
    • Spaces per gap = 3, line = "What must be".
  • Finish: Return ["What must be"].

How the Code Works (Greedy Line Packing)

Here’s the Python code with line-by-line explanation:

def fullJustify(words: list[str], maxWidth: int) -> list[str]:
    # Line 1: Initialize result
    result = []
    i = 0

    # Line 2: Process words into lines
    while i < len(words):
        # Line 3: Pack words for current line
        line_words = [words[i]]
        line_len = len(words[i])
        j = i + 1
        while j < len(words) and line_len + 1 + len(words[j]) <= maxWidth:
            line_words.append(words[j])
            line_len += 1 + len(words[j])
            j += 1

        # Line 4: Calculate spaces and gaps
        num_words = len(line_words)
        total_chars = sum(len(word) for word in line_words)
        total_spaces = maxWidth - total_chars
        gaps = num_words - 1 if num_words > 1 else 0

        # Line 5: Justify line
        if j == len(words):  # Last line, left-justified
            line = ' '.join(line_words) + ' ' * (maxWidth - total_chars - gaps)
        elif gaps == 0:  # Single word
            line = line_words[0] + ' ' * total_spaces
        else:  # Full justification
            spaces_per_gap = total_spaces // gaps
            extra_spaces = total_spaces % gaps
            line = line_words[0]
            for k in range(1, num_words):
                spaces = spaces_per_gap + (1 if k <= extra_spaces else 0)
                line += ' ' * spaces + line_words[k]

        # Line 6: Add line to result
        result.append(line)
        i = j

    # Line 7: Return justified text
    return result

Alternative: Word Grouping Approach

Explanation

Group words into lines first, then justify each group. Precompute line breaks by fitting words within maxWidth, then process each group for justification, handling the last line separately.

  1. Group Words.
  • Pack words into lines.
  1. Justify Groups.
  • Distribute spaces or left-justify.
  1. Return Result.

Step-by-Step Example (Alternative)

For ["This", "is", "an"], maxWidth = 16:

  • Start: Group ["This", "is", "an"].
  • Step 1: Fit words: 4+2+2+2=10 < 16, one line.
  • Step 2: Justify: 8 spaces, 2 gaps, 4 each -> "This is an".
  • Finish: Return ["This is an"].

How the Code Works (Word Grouping)

def fullJustifyGroup(words: list[str], maxWidth: int) -> list[str]:
    # Line 1: Group words into lines
    lines = []
    curr_line = []
    curr_len = 0
    for word in words:
        if curr_len + len(word) + len(curr_line) > maxWidth:
            lines.append(curr_line)
            curr_line = [word]
            curr_len = len(word)
        else:
            curr_line.append(word)
            curr_len += len(word)
    lines.append(curr_line)

    # Line 2: Justify each line
    result = []
    for i, line in enumerate(lines):
        if i == len(lines) - 1:  # Last line
            text = ' '.join(line)
            result.append(text + ' ' * (maxWidth - len(text)))
        else:
            chars = sum(len(word) for word in line)
            spaces = maxWidth - chars
            if len(line) == 1:
                result.append(line[0] + ' ' * spaces)
            else:
                gaps = len(line) - 1
                spaces_per_gap = spaces // gaps
                extra = spaces % gaps
                justified = line[0]
                for j in range(1, len(line)):
                    justified += ' ' * (spaces_per_gap + (1 if j <= extra else 0)) + line[j]
                result.append(justified)

    # Line 3: Return result
    return result

Complexity

  • Greedy Line Packing:
    • Time: O(n) – Process each word once.
    • Space: O(maxWidth) – Temporary line storage.
  • Word Grouping:
    • Time: O(n) – Group and justify words.
    • Space: O(n) – Store word groups.

Efficiency Notes

Greedy Line Packing is O(n) time and O(maxWidth) space, optimal for LeetCode 68 as it processes words linearly. Word Grouping is also O(n) time but may use O(n) space for storing groups, slightly less efficient but equally effective.

Key Insights

Tips to master LeetCode 68:

  • Greedy Fit: Pack words until maxWidth is exceeded.
  • Space Distribution: Evenly spread spaces, extra on left.
  • Last Line: Left-justify with trailing spaces.

Additional Example

For ["a","b"], maxWidth = 5:

  • Goal: ["a b "," "].
  • Greedy: "a b ", " ".
  • Result: ["a b "," "].

Edge Cases

  • Single Word: ["hi"], 2 – Return ["hi"].
  • Max Width Exact: ["a","b"], 3 – Return ["a b"].
  • Long Words: ["longword"], 8 – Return ["longword"].

Final Thoughts

The Greedy Line Packing solution is a stellar choice for LeetCode 68 in Python—efficient, precise, and perfect for text justification. For a related challenge, try LeetCode 67: Add Binary to switch to binary math! Ready to justify? Solve LeetCode 68 on LeetCode now and test it with ["This", "is", "an", "example"] and maxWidth=16 to master text formatting. Dive in and align those words!