Text Justification

You are tasked with implementing a text justification algorithm. This algorithm takes a list of words and a maximum line width and formats the text into lines of the specified width. The goal is to distribute spaces evenly between words to achieve a visually pleasing, justified output, similar to what you might see in books or professional documents.

Problem Description

The goal is to take an array of words and wrap them into lines of a fixed width. Each line should be filled with as many words as possible. The spaces between words on each line should be distributed as evenly as possible.

Key Requirements:

• Greedy Approach: Fill each line with as many words as possible from the input array.
• Even Space Distribution:
  • For all lines except the last one, spaces should be distributed as evenly as possible. If the total number of spaces needed to fill the line is S and there are N gaps between words, then each gap should ideally get S / N spaces.
  • Any remaining spaces ( S % N) should be distributed from left to right, adding one extra space to the leftmost gaps until all remaining spaces are used.
• Last Line Justification: The last line should be left-justified. This means words are separated by a single space, and any remaining space is appended as spaces at the end of the line.
• Single Word Lines: If a line contains only one word, it should be left-justified, with the word followed by spaces to fill the line width.

Expected Behavior:

The output should be an array of strings, where each string represents a justified line of text.

Edge Cases to Consider:

• Empty input word list.
• A single word that is longer than the maximum line width.
• A line that can only fit one word.
• The last line of the text.

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". Total characters: 3 + 2 + 2 = 7. Remaining spaces: 16 - 7 = 9. Number of gaps: 2.
9 / 2 = 4 spaces per gap. 9 % 2 = 1 extra space.
"This" + 4 spaces + "is" + 4 spaces + "an" = "This    is    an"

Line 2: "example", "of", "text". Total characters: 7 + 2 + 4 = 13. Remaining spaces: 16 - 13 = 3. Number of gaps: 2.
3 / 2 = 1 space per gap. 3 % 2 = 1 extra space.
"example" + (1+1) spaces + "of" + 1 space + "text" = "example  of text"

Line 3: "justification.". This is the last line.
"justification." is left-justified. Total characters: 14. Remaining spaces: 16 - 14 = 2.
"justification." + 2 spaces = "justification.  "

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". Total characters: 4 + 4 + 2 = 10. Remaining spaces: 16 - 10 = 6. Number of gaps: 2.
6 / 2 = 3 spaces per gap. 6 % 2 = 0 extra spaces.
"What" + 3 spaces + "must" + 3 spaces + "be" = "What   must   be"

Line 2: "acknowledgment". Total characters: 14. Remaining spaces: 16 - 14 = 2. Number of gaps: 0 (single word).
Left-justified: "acknowledgment" + 2 spaces = "acknowledgment  "

Line 3: "shall", "be". This is the last line.
"shall", "be". Total characters: 5 + 2 = 7. Remaining spaces: 16 - 7 = 9.
Left-justified: "shall" + 1 space + "be" + 8 spaces = "shall be        "

Example 3: (Edge case - single word longer than maxWidth)

Input:
words = ["a", "b", "c", "d", "e"]
maxWidth = 3

Output:
[
  "a  ",
  "b  ",
  "c  ",
  "d  ",
  "e  "
]

Explanation:
Each word is treated as a single-word line and left-justified. If a word itself is longer than maxWidth, it is placed on its own line and padded with spaces to reach maxWidth if necessary (though in this example, the single words don't exceed maxWidth).

Constraints

• 1 <= words.length <= 300
• 1 <= words[i].length <= 20
• words[i] consists of only English letters and spaces.
• 1 <= maxWidth <= 100
• words[i].length <= maxWidth (This constraint means a single word will never be longer than the line width. You only need to handle padding for single-word lines.)
• The algorithm should aim for an efficient solution. Consider the time complexity.

Notes

• The total length of words will not exceed 3 * 10^4.
• Remember to count the characters of the words themselves when calculating available space for justification.
• Pay close attention to the distinction between the last line and other lines in terms of space distribution.
• Think about how to iterate through the words array and build lines segment by segment.