class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int max_width) {
        vector<string> result;
        int start_indx = 0, end_indx = 0, input_len = words.size();

        while (start_indx < input_len) {
            int tl_char = 0, tl_words = 0;

            while (end_indx < input_len &&
                (tl_char + words[end_indx].size() + tl_words <= max_width) ) {
                tl_char  += words[end_indx].size();
                tl_words += 1;
                end_indx++;
            }

            string tmp_rslt;
            int tl_space_avail = max_width - tl_char;

            for (int i=start_indx; i < end_indx; i++) {
                tmp_rslt.append(words[i]);
                tl_words--;

                if (tl_space_avail && tl_words) {
                    int num_spaces =  0;

                    //if your are on the last line, num spaces is 1
                    if (end_indx == input_len)  {
                        num_spaces = 1;
                    } else  {
                        //calculate space for every word, tl_words is already 1 less;
                        num_spaces = (tl_space_avail % tl_words) ?
                            (tl_space_avail / tl_words) + 1 :
                            (tl_space_avail / tl_words);

                    }

                    tmp_rslt.append(num_spaces, ' ');
                    tl_space_avail -= num_spaces;
                }
            }

            //for last line or if a line has only 1 word , then tl_words = 0
            //append all the remaining spaces
            if (tl_space_avail) {
                tmp_rslt.append(tl_space_avail, ' ');
            }

            result.push_back(tmp_rslt);
            start_indx = end_indx;
        }
        return result;
    }
};