Leetcode - 418

class Solution {
    int nWords, completions;
    int getNextInd(int startInd, vector<int>& cumSentLen, int cols) {
        int remSpace = cols;
        int maxEnd;

        if(startInd > 0) {
            int remLine = cumSentLen[nWords-1] - cumSentLen[startInd-1] - 1;
            if(remLine <= remSpace) {
                remSpace -= remLine;
                startInd = 0;
                completions++;
                remSpace--;
                if(remSpace <= 0) return startInd;
            } else {
                maxEnd = remSpace + cumSentLen[startInd-1] + 1;
                auto it = upper_bound(cumSentLen.begin(), cumSentLen.end(), maxEnd);
                return it - cumSentLen.begin();
            }
        }

        int newComp = remSpace/(cumSentLen[nWords-1] + 1);
        completions += newComp;
        remSpace -= (cumSentLen[nWords-1] + 1)*newComp;
        if(remSpace == cumSentLen[nWords-1]) {
            completions++;
            remSpace = 0;
            return startInd;
        }

        auto it = upper_bound(cumSentLen.begin(), cumSentLen.end(), remSpace);
        return it - cumSentLen.begin();
    }
public:
    int wordsTyping(vector<string>& sentence, int rows, int cols) {
        nWords = sentence.size();
        completions = 0;
        vector<int> cumSentLen(nWords, 0);
        int lastSum = 0;
        for(int i = 0; i < nWords; i++) {
            if(i > 0) lastSum = cumSentLen[i-1] + 1;
            cumSentLen[i] = lastSum + sentence[i].length();
        }

        int nextInd = 0;
        for(int i = 0; i < rows; i++) {
            nextInd = getNextInd(nextInd, cumSentLen, cols);
        }
        return completions;
    }
};