Text Justification

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

Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
Output:
[
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]
Explanation: 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 becase it contains only one word.

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

---

This problem is a much harder variation of Rearrange Spaces Between Words which is here on AlgoNinjutsu, it's recommended that the previous problem should be done first.

This problem is going to come down to one overall goal; fitting as many words as we can into each string by counting the length of the characters within the words and also including the spaces required between the words, then ensuring that the total count is less than the maximum width input for each line.

That task will be achieved one of two ways; either the string will be justified left, meaning that any remaining spaces that cannot be distributed evenly should be trailing white space, or the string will be justified center, meaning that the remaining spaces will be distributed between the words instead.

To approach these two tasks we can traverse the words list with a sort of sliding window algorithm through the implementation of a left and a right pointer.  We will continue adding words to the window until the window exceeds the maximum width in which case we will form a line which we will justify based on two conditions. If we could only fit one word into the window or we are at the last line of the result, meaning we have exhausted our list of words, then we will justify left.  Otherwise, we will justify center.

---

Let's start by initializing our output array then we will begin creating our text justification helper methods.

        output = []

---

First up, we'll make the justify left function.

We'll need to know the remaining space, which is the space excluding the characters of the words that we will need to occupy to achieve the maximum width.  We'll also need a left and a right pointer to let us know how many words are within the current window that we're filling this line with.

        def justify_left(remaining_space:int, left:int, right:int) -> str:

 

We'll start filling this line by including the word at the left pointer.

            line = [words[left]]

 

Then, we will calculate how many spaces we are going to use between each word.

That calculation will be the number of words between the left and the right pointers, minus one since we don't need a space at the end.  If for example, we had three words, we would need two spaces in-between.  

We don't need to worry about fitting any remainder spaces that don't divide evenly in-between the words for our left justification, but we will in a moment for our center justification.  

            spaces_between = right - left - 1

 

Since we are justifying left, any remaining spaces will go on the right side of the line.

The right spaces will be the remaining spaces minus the spaces we are going to use in-between the words.

            right_spaces = remaining_space - spaces_between

 

For each word in between the left and the right pointer, we will append it to the line with a space.

We'll place the space before the word so that we don't have to trim any remaining spaces after the last word later, this is also the reason why we initialized the line with the leftmost word.

            for k in range(left + 1, right):
                line.append(" " + words[k])

 

Once we have done that, we will need to add the right spaces and convert the line to a string to return.

            line.append(" " * right_spaces)
            return "".join(line)

---

Next up and the most tricky, we'll make our center justification helper function.

        def justify_center(remaining_space:int, left:int, right:int) -> str:

 

Same as earlier, we'll start filling this line by including the word at the left pointer.

            line = [words[left]]
 

Then, we'll calculate the spaces needed between the words.  But note, this is only the baseline count of single spaces needed between the words, we are going to calculate how many total spaces to be placed in the next line.

            spaces_needed = right - left - 1

 

Here we will calculate the number of spaces to be distributed between the words evenly, but we'll also need the remainder as well.

            spaces_between = remaining_space // spaces_needed
            remainder = remaining_space % spaces_needed

 

Now we will build the line.

For each word between the left and the right, excluding the word we initialized the line with, we will initialize a count of new spaces which will include any remainder spaces.

            for k in range(left + 1, right):
                new_spaces = spaces_between

 

If we have a remainder, we will increment the new spaces by one and decrement the remainder count.

                if remainder:
                    new_spaces += 1
                    remainder -= 1

 

We will then fill those new spaces into the line and add the current word.

                line.append(" " * new_spaces + words[k])

 

After we have filled the line, we will convert the line to a string then return it.

            return "".join(line)

---

Now that we have our helper functions built, let's begin our sliding window to fill all of these lines.

We'll set our left pointer to the first index and also initialize a variable n so that we don't have to keep rewriting the length of the input array.

        left, n = 0, len(words)

 

While the left pointer hasn't passed the end of the input array, we still have words to fill.

        while left < n:

 

We'll start by initializing the length of our current line with the length of the word at the left pointer, then we will initialize a right pointer one index past the left.

            line_length = len(words[left])
            right = left + 1

 

Now we will add words to our window.

While the right pointer has not expanded past the end of the input length, and the current line length, plus the right word, plus the distance of our window minus one (the spaces needed between the words) has not exceeded the maximum width, we will continue adding words to our window.

            while (right < n) and (line_length + len(words[right]) + right - left - 1 < max_width):
                line_length += len(words[right])
                right += 1

 

Once we have filled our window to maximum capacity, we will calculate the remaining space we need to fill by subtracting the maximum width by the length of characters within the words of our window.

            remaining_space = max_width - line_length

 

We'll then get the word count.

            word_count = right - left

 

If the word count is one, or we are at the last line because we exhausted all of our words, then we will left-justify this line.

            if word_count == 1 or right >= n:
                output.append(justify_left(remaining_space, left, right))

 

Otherwise, we will justify center.

            else:
                output.append(justify_center(remaining_space, left, right))

 

Once we have done that, we will discard and begin a new one by moving the left pointer to the right one.

            left = right

 

After we have filled each line, we will return the output.

        return output

---