My solution was to preprocess the sentence in order to determine at each index of the sentence how many more words can fit in the column. After that I simply iterate through the rows and increment the total word count.
class Solution(object): def wordsTyping(self, sentence, rows, cols): word_nums = self.preprocess(sentence, cols) word_count = 0 for _ in xrange(rows): word_count += word_nums[word_count % len(sentence)] return word_count/len(sentence) # Preprocessing def preprocess(self, sentence, cols): word_nums =  * len(sentence) word_ptr, word_sum = 0, 0 word_len = len(sentence) for i, word in enumerate(sentence): while(word_sum + word_len <= cols): word_sum += word_len word_ptr += 1 word_len = len(sentence[word_ptr % len(sentence)]) + 1 word_nums[i] = word_ptr - i word_sum -= (len(word) + 1) return word_nums
I really like your solution, and just optimized it a little bit. The trick is that every row should have a fixed number of sentences (and fixed number of words represented as
fixed_count) occupying a fixed chunk of space. So in the preprocessing, we don't need to start at the beginning of each row, but from the
The code below runs 76 ms and beats 99.4%
class Solution(object): def wordsTyping(self, sentence, rows, cols): words = [len(word) for word in sentence] nwords, slen = len(words), sum(words) + len(words) - 1 fixed_count = (cols + 1) // (slen + 1) * len(words) start = cols + 1 - (cols + 1) % (slen + 1) if cols >= slen else 0 counts = [fixed_count] * nwords for i in range(nwords): c = 0 j = start while j + words[(i+c) % nwords] <= cols: j += words[(i+c) % nwords] + 1 c += 1 counts[i] += c words_count = 0 for i in range(rows): words_count += counts[words_count % nwords] return words_count // nwords