class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> ret = new ArrayList();
        int start = 0;
        while(start<words.length){
            StringBuilder line = new StringBuilder();
            int end = start+1;
            int cnt = words[start].length();
            while(end < words.length){
                if(cnt+words[end].length()+1>maxWidth) break;
                cnt += words[end].length()+1;
                ++end;
            }
            int dis = (end-start-1);
            int numOfSpace =(dis==0||end == words.length)?maxWidth-cnt: (maxWidth-cnt)/dis;
            int numOfSpaceExtra = dis==0?maxWidth-cnt:(maxWidth-cnt)%dis;
            while(start < end-1 && end != words.length) {
                line.append(words[start++]);
                for(int i = 0; i <= numOfSpace; ++i) {
                    line.append(" ");
                }
                if(numOfSpaceExtra > 0) {
                    line.append(" ");
                    numOfSpaceExtra--;
                }
            }
            if(end == words.length || dis==0) {
                line.append(words[start]);
                for(int i = start+1; i < end; ++i) {
                    line.append(" ");
                    line.append(words[i]);

                }
                for(int i = 0; i < numOfSpace; ++i) {
                    line.append(" ");
                }
            }else{
                line.append(words[start]);
            }

            ret.add(line.toString());
            start=end;
        }
        return ret;


    }
}