[LeetCode] 418. Sentence Screen Fitting

Given a rows x cols screen and a sentence represented by a list of non-empty 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 is greater than 0 and 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.

Thought process:
Count the total number of spaces used in the screen. The spaces used in the screen are the ones occupied by characters or the space between two words. In other words, if the screen is m * n, then the total number of spaces is m * n. But not all of those spaces are used. We need to discard the wasted spaces.
After we got the number of spaces used, divide that by the length of the sentence.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

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

Time complexity: O(rows).