418. Sentence Screen Fitting

/**

 * 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:

 * A word cannot be split into two lines. The order of words in the sentence must remain unchanged. Two consecutive

 * words in a line must be separated by a single space. Total words in the sentence won’t exceed 100. Length of each

 * word is greater than 0 and won’t exceed 10. 1 ≤ rows, cols ≤ 20,000.

*/

See the solution to the problem on git here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/google/medium/SentenceScreenFitting.java

The problem is asking how many times a sentence can fit across the screen. This translates into finding:

1. If you start at a certain word, based on the number of columns which will be the ending word as you move to next row
2. If you start from a certain word, how many sentence repeats will you have before you move from one row to the next. This is a bit tricky to conceptualize but can be considered as if you start from any word in the sentence, how many times will you reach the end of sentence before you move to the next row.
   
   
   

Based on the above concepts the algorithm is simplified as :

1. Create two arrays for record keeping
2. One that will be used to find the next word in sentence when you start with a given word as you move to the next row in the sentence
3. Second array will be used to determine how many times you reach end of the sentence when you begin with a certain word
4. Simply iterate from starting row to the ending row to the ending row while calculating number of repeats so far. 

Another aspect to note is that there can be cycles where the same starting word repeats more than once. We can further enhance the solution to calculate the number of repeats and number of rows crossed before a starting word repeats. With this we can avoid recalculating cycles and converge towards the solution quicker.  

Here is the code:

public int wordsTyping(String[] sentence, int rows, int cols) {
    int[] nextIndex = new int[sentence.length];
    int[] numberRepeatsPerWordStar = new int[sentence.length];
    for (int i = 0; i < sentence.length; i++) {
        int currWordIndex = i;
        int repeats = 0;
        int currIndex = 0;
        //loop till you reach the last column to find number of repeats that can go in a single row
        //assuming you started with a certain word. also check what would be the next word to start
        //the next row
        while (currIndex + sentence[currWordIndex].length() <= cols) {
            currIndex += sentence[currWordIndex++].length() + 1;
            if (currWordIndex == sentence.length) {
                repeats++;
                currWordIndex = 0;
            }
        }
        nextIndex[i] = currWordIndex;
        numberRepeatsPerWordStar[i] = repeats;
    }
    int totalRepeats = 0;
    int nextWordIndex = 0;
    for (int row = 0; row < rows; row++) {
        totalRepeats += numberRepeatsPerWordStar[nextWordIndex];
        nextWordIndex = nextIndex[nextWordIndex];
    }
    return totalRepeats;
}