68. Text Justification - Detailed Explanation

Problem Statement

Description:
Given an array of words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified. You must pack your words in a greedy approach; that is, pack as many words as possible in each line. Extra spaces between words should be distributed as evenly as possible. If the spaces cannot be evenly distributed, the extra spaces are assigned to the left slots first. The last line should be left-justified, and no extra space is inserted between words.

Example 1:

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

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

• Explanation:
  • Line 1: Contains "This", "is", "an".
    Total characters in words = 4 + 2 + 2 = 8.
    Spaces needed = 16 - 8 = 8, distributed in 2 gaps → each gap gets 4 spaces: "This" + " " + "is" + " " + "an".
  • Line 2: Contains "example", "of", "text".
    Total letters = 7 + 2 + 4 = 13.
    Spaces needed = 16 - 13 = 3. With 2 gaps, the left gap gets 2 spaces and the right gap gets 1 space.
  • Line 3 (Last Line): Contains "justification.".
    Left-justified with trailing spaces to reach 16 characters.

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" has 10 letters with 6 spaces distributed evenly (3 spaces per gap).
  • Line 2: Single word "acknowledgment" is left-justified with trailing spaces.
  • Line 3: Last line "shall be" is left-justified.

Constraints:

• 1 ≤ words.length ≤ 500
• 1 ≤ words[i].length ≤ maxWidth
• words[i] consists of only English letters and symbols.
• 1 ≤ maxWidth ≤ 100

Hints

1. Line Formation:
   Start by grouping words into lines such that the total length of the words plus the minimal required spaces (one space between each word) does not exceed maxWidth.

2. Space Distribution:
   For each line (except the last), calculate the total extra spaces needed (i.e., maxWidth minus the sum of the lengths of the words). Then, distribute these spaces evenly between the gaps. If the spaces cannot be evenly distributed, assign the extra spaces to the leftmost gaps.

3. Edge Cases:

   • A line with only one word should be left-justified (i.e., the word is followed by all the trailing spaces).
   • The last line must be left-justified regardless of the number of words.

Approach 1: Greedy Line Formation with Even Space Distribution

Idea

• Greedy Grouping:
  Traverse the list of words and pack as many as possible into each line until adding another word would exceed the maxWidth (considering one space between words).

• Space Distribution:

  • Non-last Line:
    Calculate the total extra spaces by subtracting the total length of the words from maxWidth.
    Then, determine the number of gaps (which is one less than the number of words in the line) and distribute the extra spaces evenly. Any remainder spaces are added one-by-one from the leftmost gap.
  • Last Line or Single-word Line:
    Left-justify the words (i.e., join them with a single space) and pad the end with spaces until the line length equals maxWidth.

Step-by-Step Walkthrough (Using Example 1)

1. Grouping Words:

   • Start with the first word "This" (length = 4).
   • Next, add "is" (length = 2) with at least 1 space → current total = 4 + 1 + 2 = 7.
   • Then, add "an" (length = 2) → current total = 7 + 1 + 2 = 10.
   • Trying to add "example" (length = 7) would exceed 16 (10 + 1 + 7 = 18), so stop grouping.
   • Line 1 Words: ["This", "is", "an"]

2. Distributing Spaces for Line 1:

   • Total letters = 4 + 2 + 2 = 8.
   • Spaces required = 16 - 8 = 8.
   • Number of gaps = 2.
   • Each gap gets 8 / 2 = 4 spaces (no remainder).
   • Line 1: "This" + " " + "is" + " " + "an" = "This is an"

3. Repeat for Subsequent Lines:

   • Line 2: Process "example", "of", "text".
     • Total letters = 7 + 2 + 4 = 13, spaces = 16 - 13 = 3, gaps = 2.
     • First gap gets 2 spaces, second gets 1.
     • Line 2: "example" + " " + "of" + " " + "text" = "example of text"
   • Line 3 (Last Line):
     • Contains "justification." (length = 14).
     • Left-justify by appending trailing spaces: "justification." + " " = "justification. ".

Complexity Analysis

• Time Complexity: O(n * k)
  (We iterate over each word once, and constructing each line involves processing each character in the words.)
• Space Complexity: O(n * k)
  (For storing the output, which in worst-case is proportional to the number of words and their lengths.)

Python Code (Greedy Approach)