68. Text Justification

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        result = []
        i = 0

        while i < len(words):
            j = i
            line_length = 0

            while j < len(words):
                needed = line_length + len(words[j]) + (j - i)

                if needed > maxWidth:
                    break

                line_length += len(words[j])
                j += 1

            line_words = words[i:j]
            gaps = len(line_words) - 1

            if j == len(words) or gaps == 0:
                line = " ".join(line_words)
                line += " " * (maxWidth - len(line))

            else:
                total_spaces = maxWidth - line_length
                spaces_each = total_spaces // gaps
                extra = total_spaces % gaps

                line = ""

                for k in range(gaps):
                    line += line_words[k]
                    line += " " * spaces_each

                    if k < extra:
                        line += " "

                line += line_words[-1]

            result.append(line)
            i = j

        return result