class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> list = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        int count = 0;
        int wordnum = 0, index = 0;
        while (index < words.length){
            if(count + wordnum + words[index].length() > maxWidth){ //超過
                if(wordnum == 1){
                    sb.append(words[index-1]);
                    while(sb.length() < maxWidth){
                        sb.append(' ');
                    }
                    list.add(sb.toString());
                    sb = new StringBuilder();
                    wordnum = 0;
                    count = 0;
                    continue;
                }
                int spacelen = maxWidth - count;
                int eachspace = spacelen / (wordnum-1);
                int extraspace = spacelen % (wordnum-1);
                StringBuilder space = new StringBuilder();
                for(int i = 0; i < eachspace; i++){
                    space.append(' ');
                }
                for(int i = 0; i < extraspace; i++){
                    sb.append(words[index - wordnum + i]);
                    sb.append(space);
                    sb.append(' ');
                }
                for(int i = extraspace; i < wordnum-1; i++){
                    sb.append(words[index - wordnum + i]);
                    sb.append(space);
                }
                sb.append(words[index - 1]);
                list.add(sb.toString());
                sb = new StringBuilder();
                count = 0;
                wordnum = 0;
            }
            else if(count + wordnum + words[index].length() <= maxWidth){
                count +=  words[index].length();
                wordnum++;
                index++;
            }
        }
        for(int i = wordnum-1; i >= 0; i--){
            sb.append(words[words.length - 1 -i]);
            sb.append(' ');
        }
        sb.deleteCharAt(sb.length()-1);
        while (sb.length() < maxWidth){
            sb.append(' ');
        }
        list.add(sb.toString());
        return list;
    }
}