Problem Statement in English

You’re given an array of strings words and a width maxWidth. You need to format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.

The last line should be left-justified, and no extra space is inserted between words.

Return the formatted text as an array of strings, where each string represents a line of text.

Approach

Since for each line the number of whitespaces between words can be calculated using the number of characters in the words and the number of words, we can iterate through the list of words and keep track of the number of characters and the number of words in the current line. When we reach a word that would make the line exceed maxWidth, we can assemble the line using the words we’ve collected so far, and then reset our counters for the next line.

Assembling the line involves calculating the number of spaces to insert between words. If it’s the last line or if there’s only one word in the line, we can simply left-justify the line by joining the words with a single space and adding any remaining spaces at the end. Otherwise, we calculate the number of spaces to distribute evenly between words, and if there are any extra spaces, we distribute them starting from the left.

Finally, we return the list of formatted lines.

And we’re done!

Solution in Python


class Solution:
    def fullJustify(self, words: list[str], maxWidth: int) -> list[str]:
        l = c_chars = c_word_count = 0
        res = []

        def assemble(r, lastLine):
            nonlocal l, c_word_count, c_chars

            if lastLine or c_word_count == 1:
                buffer = " ".join(words[l : r + 1])
                buffer += " " * (maxWidth - len(buffer))
                res.append(buffer)
                return

            gaps = maxWidth - c_chars
            gap = gaps // (c_word_count - 1)
            spare = gaps % (c_word_count - 1)

            buffer = ""
            for i in range(l, r):
                buffer += words[i]
                buffer += " " * gap
                if spare > 0:
                    buffer += " "
                    spare -= 1
            
            buffer += words[r]
            res.append(buffer)

        for i, word in enumerate(words):
            wordLen = len(word)

            if c_chars + c_word_count + wordLen > maxWidth:
                assemble(i - 1, False)
                c_chars = wordLen
                c_word_count = 1
                l = i
            else:
                c_chars += wordLen
                c_word_count += 1

        assemble(len(words) - 1, True)

        return res

Complexity

  • Time: $O(n)$
    Since we are iterating through the list of words once, the time complexity is linear with respect to the number of words.

  • Space: $O(n)$
    Since we are storing the result in a list, the space complexity is linear with respect to the number of words.

Mistakes I Made

I missed some edge cases.

And we are done.