Text Justification

hardFREEStrings & ArraysLinkedIn DSA

Given words and a maxWidth, format text with full justification: each line has exactly maxWidth characters, spaces distributed evenly. Last line is left-justified.

Input: first line = comma-separated words, second = maxWidth.

Example

Input

This,is,an,example,of,text,justification.
16

Output

This    is    an
example  of text
justification.

Reasoning

The input words are split into an array: ["This", "is", "an", "example", "of", "text", "justification"].
We iterate through the words, distributing them into lines with a maximum width of $16$ characters, including spaces. The first line can fit ["This", "is", "an"], requiring $3$ spaces to be added for even distribution: $5+2+2+3=12$ , and $4$ more spaces are added to reach the maximum width.
The second line can fit ["example", "of", "text"], requiring $2$ spaces between each word and $1$ space at the end to reach a width of $15$ , then one more space is added to reach the maximum width of $16$ .
The last line is left-justified and contains the remaining word ["justification"], which is shorter than the maximum width, so it is printed as is.

Constraints

1 <= len(words) <= 300
1 <= len(words[i]) <= 20
1 <= maxWidth <= 100

Background Knowledge

The Text Justification problem involves formatting a given list of words into lines of text with a specified maximum width, ensuring that each line has exactly maxWidth characters. This requires understanding of string manipulation and array operations. To solve this problem, one needs to consider how to distribute spaces evenly between words to achieve full justification. The concept of full justification means that each line of text should have the same width, with spaces added as needed to fill the line.

The problem also involves understanding how to handle the last line of text, which is left-justified. This means that the last line should have the words separated by a single space, with no additional spaces added to fill the line. To approach this problem, one needs to consider the length of each word, the total length of all words, and the number of spaces needed to fill each line. Additionally, understanding how to calculate the average number of spaces to add between words and how to handle cases where the average number of spaces is not an integer is crucial.

The problem can be broken down into smaller sub-problems, such as calculating the total length of all words in a line, determining the number of spaces needed to fill the line, and distributing the spaces evenly between the words. This requires a solid understanding of basic arithmetic operations, such as addition, subtraction, multiplication, and division, as well as integer division and modulus operations.

Algorithm/Approach

The general approach to solving this type of problem involves using a greedy algorithm, where we make the locally optimal choice at each step with the hope that it will lead to a globally optimal solution. In this case, we can iterate through the list of words, adding each word to the current line and checking if the line would exceed the maximum width. If it would exceed the maximum width, we can justify the current line by adding spaces and then move on to the next line.

Step-by-Step Strategy

To implement the solution, we can follow these steps:

Split the input string into a list of words
Initialize an empty list to store the justified lines of text
Iterate through the list of words, adding each word to the current line and checking if the line would exceed the maximum width
If the line would exceed the maximum width, justify the current line by adding spaces and add it to the list of justified lines
Repeat the process until all words have been processed
Justify the last line by left-justifying it

Common Pitfalls

Some common pitfalls to watch out for when implementing this solution include:

Not handling the case where the last line is left-justified
Not calculating the correct number of spaces to add between words
Not handling cases where the average number of spaces is not an integer
Not checking for edge cases, such as an empty list of words or a maximum width of 0

Time & Space Complexity

The expected time complexity for this solution is O(n), where n is the number of words, since we are iterating through the list of words once. The expected space complexity is also O(n), since we are storing the justified lines of text in a list. The space complexity can be reduced by only storing the current line of text and the list of justified lines, rather than storing all intermediate lines.

solution.py

Python 3.13

Test results