Problem statement

https://leetcode.com/problems/sentence-screen-fitting/

Solution

We can do it word by word, but it can be potentially too slow. Let us merge all words into sequence with spaces, for example “I have a cat “. Then we try to traverse line by line, how we do it? We have start value, which indicates how much symbols we traverse. For each line we do start += cols. Then we evaluate seq[start \% N], where N is length of our concatenated string. If we have space, we can safely go the the next line and we just do start += 1. If symbol is not space, we go back until we meet space symbol. In the end we return start//N.

Complexity

Time complexity is is $O(cols + N)$, space complexity is $O(N)$.

Code

class Solution:
    def wordsTyping(self, sentence, rows, cols):
        seq = " ".join(sentence) + " "
        N, start = len(seq), 0
        for i in range(rows):
            start += cols
            if seq[start % N] == " ":
                start += 1
            else:
                while start > 0 and seq[(start-1)%N] != " ":
                    start -=1
        return start // N