Sentence Screen Fitting LeetCode Solution

Problem Statement:

Sentence Screen Fitting LeetCode Solution: 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.

Examples:

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.

Approach:

Idea:

The idea is to first concatenate the entire set of words into a single word (let’s say “concat“) separated by space, and then check how many times we can fit it into the screen. We keep a pointer to check which character of concat we are currently pointing to. For each row, we will check the maximum part of concat we can store. The pointer will get incremented on the basis of the column size of the screen and then we will check what character the pointer is pointing to. If it is a ” ” then it is fine, else we need to trace back to find the previous occurrence of ” “. Check out the code for a better understanding.

Code:

Sentence Screen Fitting C++ Solution:

class Solution {
public:
    int wordsTyping(vector<string>& sentence, int rows, int cols) {
        string concat = "";
        for(auto it:sentence){
            concat += it + " ";
        }
        int n = concat.size();
        int ptr = 0;
        for(int r=0;r<rows;r++){
            ptr += cols;
            if(concat[ptr%n] == ' ')
                ptr++;
            else{
                while(ptr>0 and concat[(ptr-1)%n] != ' ')
                    ptr--;
            }
        }
        return ptr/n;
    }
};

Sentence Screen Fitting Python Solution:

class Solution:
    def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:
        concat = " ".join(sentence) + " "
        n = len(concat)
        ptr = 0
        for r in range(rows):
            ptr += cols
            if concat[ptr%n] == " ":
                ptr += 1
            else:
                while ptr>0 and concat[(ptr-1)%n] != " ":
                    ptr -= 1
        
        return ptr//n

Complexity Analysis of Sentence Screen Fitting LeetCode Solution:

• Time Complexity: The time complexity of the above code is O(rows*length_of_max_word).
• Space Complexity: The space complexity of the above code is O(sum of the length of words).