418. Sentence Screen Fitting

Given a rows x cols screen and a sentence represented as a list of strings, return the number of times the given sentence can be fitted on the screen.

The order of words in the sentence must remain unchanged, and a word cannot be split into two lines. A single space must separate two consecutive words in a line.

Example 1:

Input: sentence = ["hello","world"], rows = 2, cols = 8
Output: 1
Explanation:
hello---
world---
The character '-' signifies an empty space on the screen.

Example 2:

Input: sentence = ["a", "bcd", "e"], rows = 3, cols = 6
Output: 2
Explanation:
a-bcd- 
e-a---
bcd-e-
The character '-' signifies an empty space on the screen.

Example 3:

Input: sentence = ["i","had","apple","pie"], rows = 4, cols = 5
Output: 1
Explanation:
i-had
apple
pie-i
had--
The character '-' signifies an empty space on the screen.

Constraints:

• 1 <= sentence.length <= 100

• 1 <= sentence[i].length <= 10

• sentence[i] consists of lowercase English letters.

• 1 <= rows, cols <= 2 * 104

Solution

Intuition :

The brute force: To put the sentence into the matrix, to see how many rounds we can reach.

Optimal:

• To format the roundString,

• Iterate the rows, and calculate how many usedSpace will be when we put the roundString into matrix repeatedly.

    public int wordsTyping(String[] sentence, int rows, int cols) {
        String roundString = String.join(" ", sentence) + " ";
        int len = roundString.length();
        int usedSpace = 0;
        for(int i = 0; i < rows; i++){
            usedSpace += cols;
            if(roundString.charAt(usedSpace%len) == ' '){
                usedSpace++; // give an extra space for ' ' to meet the roundString
            }else{
                while(usedSpace > 0 && roundString.charAt((usedSpace-1)%len) != ' '){
                    usedSpace--; //reduce the usedSpace to char which next to the last ' '
                }
            }
        }
        return usedSpace / len;
    }