Sentence Screen Fitting - Leetcode Solution

Problem Statement:

Given a rows x cols screen and a sentence represented as 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.

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.

Approach:

The brute force approach to this problem would be to simulate the typing of the sentence on the screen. We start from the top-left corner and keep filling the rows until we can't fit anymore. Then we move to the next row until we've filled the screen. After we've filled the screen, we count the number of times we've filled the sentence on the screen and return the count.

However, this approach would be very time-consuming and wouldn't work for larger inputs. We need to come up with an optimized approach that doesn't involve simulating the screen.

We can consider the sentence as a single long string and use two pointers, i and j, to keep track of the range of characters that can fit on a row. We move the pointer i to the last valid position that can fit on the row and increment the row count. We repeat this process until we've filled the screen.

But how do we determine if a word can fit on the row? We can use the length of the word and the remaining space on the row to determine this. If the length of the word is greater than the remaining space, we move to the next row and update the remaining space with the full width of the screen minus the length of the word (to account for the space between words).

We then repeat this process until we've filled the screen completely. We keep a count of the number of times we've filled the sentence on the screen and return the count.

Solution:

Let L be the length of the sentence as a single string, and let n be the number of words in the sentence.

Step 1: Concatenate all the words of the sentence into a single string with spaces between them.

Step 2: Initialize a pointer i to 0 that points to the first character of the sentence.

Step 3: Initialize a variable count to 0 that keeps track of the number of times the sentence can be fitted on the screen.

Step 4: For each row on the screen, initialize a variable j to 0 that points to the first character of the row.

Step 5: While there are still characters left in the row, calculate the maximum number of characters that can fit on the row between indices i and i + j - 1.

• If the maximum number of characters that can fit on the row is less than the length of the next word, move on to the next row.
• Otherwise, move the pointer i to the last character in the current row and increment the row count.

Step 6: Repeat Step 5 until we've filled the entire screen.

Step 7: Return the count as the answer.

Here's the Python code for the solution:

def wordsTyping(sentence, rows, cols): full_string = ' '.join(sentence) + ' ' # Concatenate the sentence into a single string with spaces between words i = 0 # Initialize a pointer i to the first character of the sentence count = 0 # Initialize a variable count to 0 that keeps track of the number of times the sentence can be fitted on the screen for r in range(rows): # For each row on the screen j = 0 # Initialize a variable j to 0 that points to the first character of the row while j < cols: # While there are still characters left in the row if full_string[i % len(full_string)] == ' ': # If the next character is a space i += 1 # Move the pointer i to the next character elif i > len(full_string) - 1 - j % len(full_string) - 1: # If the next word doesn't fit on the row break # Move on to the next row else: # Otherwise, move the pointer i to the last character in the current row i += 1 # And increment the row count j += 1 # Move the pointer j to the next character in the row if j == cols: # If we've filled the entire row count += 1 # Increment the row count return count # Return the answer

Time Complexity:

The time complexity of this algorithm is O(n * (cols + L)), where n is the number of words in the sentence and L is the length of the sentence as a single string. This is because we need to iterate over each row of the screen and for each row, we need to scan through the sentence to find the maximum number of characters that can fit on the row. The worst-case scenario occurs when the sentence can only fit one word on a row, which requires us to scan through the entire sentence for each row.

Space Complexity:

The space complexity of this algorithm is O(L), where L is the length of the sentence as a single string. This is because we only need to store the concatenated sentence as a single string.

1