[Google Question][LeetCode] Sentence Screen Fitting

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

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

Output: 
1

Explanation:
hello---
world---

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

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.

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.

Approach: Let's try the simple approach first. The approach is simple where we try to fit as many words on the row and when we find that we can't have more words on current row, we went to next row. Whenever we reach to the end of sentence array, we start from the first word of the sentence. Not much to explain, you can directly go to implementation and understand the approach.

Let's move to our second which is bit complex solution. Basically if you see we are trying to fit words into row in our first approach. In this approach we first form an string say 'words' by joining all the words in the sentence with a space and then see on every row what is the max total valid characters of words can put. We already know that we can have at most 'cols' characters. We add it to total_valid_length. Now if we find words[total_valid_length % length of words] is space (' '), then we know that we have added valid words but if it is not space then we have to decrease total_valid_length till we get the space because we can only adjust these many words in the row. In the end total_valid_length % length of words is our answer.

That's all!

Implementation in C#:

Approach 1: Brute force

    public int WordsTyping(string[] sentence, int rows, int cols) 

    {    

        int len = sentence.Length;

        int[] sentenceLength = new int[len];

        for (int index = 0; index < len; ++index)

        {

            sentenceLength[index] = sentence[index].Length;

        }

        int i = 0, row = 0, spaceRemaining = cols, cycle = 0;

        while (row < rows)

        {

            while (sentenceLength[i] <= spaceRemaining)

            {

                spaceRemaining -= sentenceLength[i] + 1;

                ++i;

                if (i == len)

                {

                    i = 0;

                    ++cycle;

                }

            }            

            ++row;

            spaceRemaining = cols;

        }  

        return cycle;

    }

Approach 2: Joining the words and then look for valid length

    public int WordsTyping(string[] sentence, int rows, int cols) 

    {    

        string words = string.Join(' ', sentence) + ' ';

        int wordsLen = sentences.Length;

        int totalProcessedLen = 0;

        for (int i = 0; i < rows; ++i)

        {

            totalProcessedLen += cols;

            if (words[totalProcessedLen % wordsLen] == ' ')

            {

                ++totalProcessedLen;

            }

            else

            {

                while (totalProcessedLen >= 0 && words[totalProcessedLen % wordsLen] != ' ')

                {

                    --totalProcessedLen;

                }

                ++totalProcessedLen;

            }

        }

        return totalProcessedLen / wordsLen;

    }

Complexity: Approach 1: O(rows * cols), Approach 2: O(rows * length of the word with maximum length in the sentence)