Sentence Screen Fitting

Given a rows x cols screen and a sentence represented by a list of words, find how many times the given sentence can be fitted on the screen.

Note:

1. A word cannot be split into two lines.
2. The order of words in the sentence must remain unchanged.
3. Two consecutive words in a line must be separated by a single space.
4. Total words in the sentence won't exceed 100.
5. Length of each word won't exceed 10.
6. 1 ≤ rows, cols ≤ 20,000.

Example 1:

Input:
rows = 2, cols = 8, sentence = ["hello", "world"]

Output: 
1

Explanation:
hello---
world---

The character '-' signifies an empty space on the screen.

Example 2:

Input:
rows = 3, cols = 6, sentence = ["a", "bcd", "e"]

Output: 
2

Explanation:
a-bcd- 
e-a---
bcd-e-

The character '-' signifies an empty space on the screen.

Example 3:

Input:
rows = 4, cols = 5, sentence = ["I", "had", "apple", "pie"]

Output: 
1

Explanation:
I-had
apple
pie-I
had--

The character '-' signifies an empty space on the screen.

A naive approach is to go through the screen and put each word in it. Whenever we find a word doesn't fit to the left cells, we switch to the next line. This approach is slow. Here is a way to optimize:

We first concatenate all strings together and add spaces between words. This string is the actual length we need to fit the string. Now we have a pos variable that initializes to 0, this is the position in the All string. Now for each row, we add cols to pos, this is the position in the All string that we can fit in the row. If the pos in the All string is pointing to a white space, we know we have just fitted (at least partial) strings in it. pos increment by 1. If its a letter, we know its in the middle of the word, so we need to decrease the pos to the start of the word. Here using pos % len indicates if pos is larger than len, it will go back to a position in the string.

public int wordsTyping(String[] sentence, int rows, int cols) {
        String all = "";
        for (String s : sentence) {
            all += s + " ";
        }
        int pos = 0;
        int len = all.length();
        for (int i = 0; i < rows; i++) {
            pos += cols;
            if (all.charAt(pos % len) == ' ') {
                pos++;
            } else {
                while (pos > 0 && all.charAt((pos - 1) % len) != ' ') {
                    pos--;
                }
            }
        }
        return pos / len;
    }