public class Solution {
    public IList<string> FullJustify(string[] words, int maxWidth) {
        IList<string> res = new List<string>();
        int i = 0;
        int chLength = 0; //字符所占的长度
        int wordLength = 0; //单词个数
        
        int space = 0;
        
        while(i < words.Length)
        {
            string word = words[i];
            if(wordLength + chLength + word.Length <= maxWidth)
            {
                wordLength++;
                chLength += word.Length;
                i++;      
                continue;
            }
            
            space = maxWidth - chLength;
            if(wordLength == 0) return res;
            if(wordLength == 1)
            {
                res.Add(words[i - 1].PadRight(maxWidth, ' '));    
            }
            else
            {
                int wordSpace = space / (wordLength - 1);
                int extraSpace = space % (wordLength - 1);
                int start = i - wordLength;
                string cur = string.Empty;
                for(int j = start; j < start + extraSpace; j++)
                {
                    cur += words[j];
                    cur += new string(' ', wordSpace + 1);
                }
                for(int j = start + extraSpace; j < i - 1; j++)
                {
                    cur += words[j];
                    cur += new string(' ', wordSpace);
                }
                cur += words[i - 1];
                res.Add(cur);
            }     
            chLength = 0;
            wordLength = 0;
        }
        //加上最后一行
        if(wordLength == 0) return res;
        space = maxWidth - chLength;
        if(wordLength == 1)
        {
            res.Add(words[i - 1].PadRight(maxWidth, ' '));     
        }
        else
        {
            int start = i - wordLength;
            string cur = string.Empty;

            for(int j = start; j < i - 1; j++)
            {
                cur += words[j];
                cur += ' ';
            }
            cur += words[i - 1];
            
            res.Add(cur.PadRight(maxWidth, ' '));
        }     
        return res;
    }
}

class Solution:
    def fullJustify(self, words, maxWidth):
        """
        :type words: List[str]
        :type maxWidth: int
        :rtype: List[str]
        """
        res, cur, num_of_letters = [], [], 0
        for w in words:
            if num_of_letters + len(w) + len(cur) > maxWidth:
                for i in range(maxWidth - num_of_letters):
                    cur[i%(len(cur)-1 or 1)] += ' '
                res.append(''.join(cur))
                cur, num_of_letters = [], 0
            cur += [w]
            num_of_letters += len(w)
        return res + [' '.join(cur).ljust(maxWidth)]