Problem Description

The Sentence Screen Fitting problem asks you to determine how many times a given sentence can fit on a screen with specified rows and columns.

You are given:

• An array of strings sentence, where each string is a single word. The sentence should be repeated as many times as possible.
• Two integers rows and cols indicating the number of rows and columns on the screen.

• Each word length is at least 1 and at most cols (no word will be longer than the number of columns).
• Words cannot be split between rows.
• You must return the total number of times the entire sentence can fit on the screen.

Thought Process

At first glance, a brute-force solution seems straightforward: for each row, try to fit as many words as possible, wrapping to the next row when necessary, and count how many times the sentence is completed.

However, with large rows and cols, this approach would be too slow. We need to optimize.

The key insight is that the process is repetitive. The way words wrap on each row depends only on where we left off in the sentence and the current column. If we can track and cache the starting word index for each row, we can skip redundant work by using this pattern.

Instead of simulating every character, we can treat the sentence as a single string with spaces and see how many characters fit on the screen. By using modular arithmetic and precomputing, we can efficiently compute the result.

Solution Approach

Here’s a step-by-step breakdown of the optimized approach:

1. Concatenate the sentence:
   • Join all words in sentence into a single string with spaces, plus a trailing space (e.g., "hello world ").
2. Simulate filling the screen row by row:
   • Use a variable start to keep track of how many characters have been placed so far.
   • For each row, increment start by cols (the number of columns).
   • If the character at start % length_of_sentence is a space, increment start by 1 (start the next word in the next column).
   • If not, decrement start until it's at a space (back up to the last word boundary).
3. Count the number of times the sentence fits:
   • After all rows are processed, start // length_of_sentence gives the total number of times the sentence fits on the screen.

• By simulating the process using a concatenated string, we avoid word-by-word iteration and can efficiently jump to the next valid position.
• This method ensures no word is split between rows and respects all constraints.

Example Walkthrough

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

Step-by-step:

• Concatenate sentence: "hello world " (length = 12)
• Initialize start = 0
• Row 1:
  • start += 8 → start = 8
  • sentence[start % 12] = 'r' (not a space), so backtrack to the last space:
    • start = 7 ('o'), start = 6 ('w'), start = 5 (' ')
  • Now at a space, increment start to 6 for the next word.
• Row 2:
  • start += 8 → start = 14
  • 14 % 12 = 2, character is 'l' (not a space), so backtrack:
    • start = 13 ('e'), start = 12 ('h'), start = 11 (' ')
  • Now at a space, increment start to 12 for the next word.
• Result:
  • start = 12
  • 12 // 12 = 1

Time and Space Complexity

Brute-force approach:

• Time Complexity: O(rows * cols) because you simulate every cell in the grid.
• Space Complexity: O(1) (not counting input).

• Time Complexity: O(rows * cols / length_of_sentence) in the worst case, but typically much faster due to skipping over words efficiently.
• Space Complexity: O(L) where L is the length of the concatenated sentence string.

Summary

The Sentence Screen Fitting problem is about efficiently simulating how a sentence fits repeatedly on a screen of given dimensions, without splitting words or violating constraints. The key insight is to represent the sentence as a single concatenated string and simulate the filling process by tracking positions within this string, allowing us to efficiently compute the result without brute-force simulation. This approach leverages modular arithmetic and careful handling of word boundaries, resulting in a clean, fast, and elegant solution.

Code Implementation

class Solution:
    def wordsTyping(self, sentence, rows, cols):
        s = ' '.join(sentence) + ' '
        start = 0
        l = len(s)
        for _ in range(rows):
            start += cols
            if s[start % l] == ' ':
                start += 1
            else:
                while start > 0 and s[(start - 1) % l] != ' ':
                    start -= 1
        return start // l
      

class Solution {
public:
    int wordsTyping(vector<string>& sentence, int rows, int cols) {
        string s;
        for (const string& word : sentence) {
            s += word + " ";
        }
        int start = 0, l = s.size();
        for (int i = 0; i < rows; ++i) {
            start += cols;
            if (s[start % l] == ' ') {
                ++start;
            } else {
                while (start > 0 && s[(start - 1) % l] != ' ') {
                    --start;
                }
            }
        }
        return start / l;
    }
};
      

class Solution {
    public int wordsTyping(String[] sentence, int rows, int cols) {
        StringBuilder sb = new StringBuilder();
        for (String word : sentence) {
            sb.append(word).append(" ");
        }
        String s = sb.toString();
        int start = 0, l = s.length();
        for (int i = 0; i < rows; ++i) {
            start += cols;
            if (s.charAt(start % l) == ' ') {
                start++;
            } else {
                while (start > 0 && s.charAt((start - 1) % l) != ' ') {
                    start--;
                }
            }
        }
        return start / l;
    }
}
      

var wordsTyping = function(sentence, rows, cols) {
    let s = sentence.join(' ') + ' ';
    let start = 0, l = s.length;
    for (let i = 0; i < rows; ++i) {
        start += cols;
        if (s[start % l] === ' ') {
            start++;
        } else {
            while (start > 0 && s[(start - 1) % l] !== ' ') {
                start--;
            }
        }
    }
    return Math.floor(start / l);
};