418

class Solution {
public:
    int wordsTyping(vector<string>& sentence, int rows, int cols) {
        unordered_map<int, int> umap;
        int num = 0, n = sentence.size();

        // Each row will start with some word.
        // So better maintain a map that if we start from word x, we will cover cnt number of words.
        // Count the total number of words that can be fit in the given rows, divide it by number of
        // words in sentence to get number of lines required.
        for(int i = 0; i < rows; i++){
            int start = num % n;
            if(umap.count(start) == 0){
                int cnt = 0, len = 0;
                for(int i = start; len < cols; i = (i+1) % n, cnt++){
                    if(len + sentence[i].size() > cols)
                        break;
                    len += sentence[i].size() + 1;
                }
                num += cnt;
                umap.emplace(start, cnt);
            }
            else
                num += umap[start];
        }
        return num / n;
    }
};