import pytest
import pdb
from typing import List

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        """
        """
        
        def intertwine(ws, sps):
            # one word + one sps appended
            t = []
            for w, s in zip(ws, sps):
                t.extend([w, s])
            t.append(ws[-1])
            return ''.join(t)
        
        
        # 1. Greedy pick words for each line
        cur_count = 0
        buffer = []
        lines = []
        for w in words:
            if (cur_count + len(w) + (1 if cur_count else 0)) <= maxWidth:
                cur_count += len(w) + (1 if cur_count else 0)
            else:
                lines.append(buffer)
                cur_count = len(w)
                buffer = []
            buffer.append(w)
        if buffer:
            lines.append(buffer)
        
        # 2. Justify spaces using divmod
        for i in range(len(lines)):
            remaining = maxWidth - (sum(len(w)+1 for w in lines[i]) - 1)
            
            # Left justify last line
            if i == len(lines)-1:
                lines[i] = ' '.join(lines[i]) + ' '*remaining
                
            # Full justify
            else:
                if len(lines[i]) > 1:
                    interval, left = divmod(remaining, len(lines[i])-1)
                    spaces = [' ' *(1+interval+ (1 if j < left else 0)) for j, w in enumerate(lines[i])][:-1]
                    lines[i] = intertwine(lines[i], spaces)
                else:
                    # Left justfiy if only 1 word per line
                    lines[i] = ' '.join(lines[i]) + ' '*remaining
        
        return lines
            
            
        
         

@pytest.mark.parametrize('input, length, output', [
    (["This", "is", "an", "example", "of", "text", "justification."],16,["This    is    an", "example  of text", "justification.  "]),
    (["Listen","to","many,","speak","to","a","few."], 6,["Listen","to    ","many  ,","speak ","to   a","few.  "])
])
def test(input, length, output):
    Solution().fullJustify(input, length) == output

if __name__ == '__main__':
    sys.exit(pytest.main(['-s', '-v'] + sys.argv))
