Problem statement

https://leetcode.com/problems/text-justification/

Solution

Not difficult, but technical problem. Let us keep buffer: list of words to fill the last line so far and curr_len is how much space it will take if we use only one space between words.

Iterate through words and check if we can add word to buffer: if we can, add it, if not, it means that we need to build string. Calculate number of empty spaces empty and number of gaps places. If places == 0, we need to use only one word in string. If it is more than zero, find a, b = divmod(empty, places) and then for each word add a spaces after word and also for first b words add one extra space. In the end concatenate everything and add to ans. Finally add last not-full string.

Complexity

Time complexity is just O(n), where n is total length of words: we traverse every word once. Also it can be shown, that final answer will consist no more than 3n to 4n symbols (cases something like words = [a, a, aaaaaaaaaa, aaaaaaaaaa], maxWidth = 20, so all adding of spaces will not break complexity. Space complexity is O(n) as well.

Code

class Solution:
    def fullJustify(self, words, maxWidth):
        buffer, curr_len = [words[0]], len(words[0])
        ans = []
        for i, word in enumerate(words[1:]):
            if curr_len + len(word) + 1 <= maxWidth:
                buffer.append(word)
                curr_len += len(word) + 1
            else:
                empty = maxWidth - curr_len + len(buffer) - 1
                places = len(buffer) - 1
                if places == 0: 
                    ans.append(buffer[0] + " "*(maxWidth - len(buffer[0])))
                else:
                    a, b = divmod(empty, places)
                    for i in range(places): buffer[i] += " "*a
                    for i in range(b): buffer[i] += " "
                    ans.append("".join(buffer))
                buffer, curr_len = [word], len(word)
        
        t = " ".join(buffer)
        return ans + [t + " "*(maxWidth - len(t))]