class Solution {
    int MAX_WIDTH;
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<>();
        int i = 0;
        int n = words.length;
        MAX_WIDTH = maxWidth;
        while(i < n){
            int lettersCount = words[i].length();
            int spaceCount = 0;
            int j = i+1;
            while(j<n && lettersCount+spaceCount+words[j].length()+1<=maxWidth){
                lettersCount+= words[j].length();
                spaceCount+= 1;
                j++;
            }
            int remainingSpaces = maxWidth - lettersCount;
            int numSlots = spaceCount == 0 ? 0 : remainingSpaces / spaceCount;
            int extraSpaces = spaceCount == 0 ? 0 : remainingSpaces % spaceCount;
            if(j == n){
                //last line must be left justified
                numSlots = 1;
                extraSpaces = 0;
            }
            String toBeAdded = findLine(words, i, j, numSlots, extraSpaces);
            res.add(toBeAdded);
            i=j;

        }
        return res;
    }

        String findLine(String[] words, int i, int j, int numSlots, int extraSpaces){
            StringBuilder line = new StringBuilder();
            for(int k=i ;k<j; k++){
                line.append(words[k]);
                if(k == j-1){
                    //last word of line
                    continue;
                }
                for(int l=1;l<=numSlots;l++){
                    line.append(" ");
                }
                if(extraSpaces > 0){
                    line.append(" ");
                    extraSpaces--;
                }
            }
            while(line.length() < MAX_WIDTH){
                line.append(" ");
            }
            return line.toString();
        }
}