LeetCode 418: Sentence Screen Fitting

Problem Restatement

We are given:

We want to place the sentence repeatedly on the screen.

Rules:

1. Words must appear in the original order.
2. A word cannot be split across lines.
3. Consecutive words are separated by one space.
4. The sentence repeats cyclically.

Return how many complete times the sentence fits on the screen.

The source examples include:

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

whose answer is 1.

The constraints include:

1 <= sentence.length <= 100
1 <= rows, cols <= 20000
1 <= word.length <= 10

(leetcode.com)

Input and Output

Example function shape:

def wordsTyping(sentence: list[str], rows: int, cols: int) -> int:
    ...

Examples

Example 1:

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

The answer is:

1

Screen layout:

hello---
world---

The sentence fits exactly once.

Example 2:

sentence = ["a", "bcd", "e"]
rows = 3
cols = 6

The answer is:

2

One valid layout:

a-bcd-
e-a---
bcd-e-

The sentence repeats twice completely.

Example 3:

sentence = ["i", "had", "apple", "pie"]
rows = 4
cols = 5

The answer is:

1

First Thought: Simulate Word by Word

A direct approach is:

1. Track the current word index.
2. Fill each row greedily.
3. Count how many times we return to word 0.

This works, but repeatedly checking words and spaces row by row can become verbose.

We can simplify the process using a cyclic sentence string.

Key Insight

Join the sentence into one cyclic string:

s = "hello world "

Notice the trailing space.

Now the sentence behaves like an infinite repeating string:

hello world hello world hello world ...

For each row:

1. Pretend we advance exactly cols characters.
2. If we land on a space, we can start the next row immediately after that space.
3. Otherwise, we landed in the middle of a word, so move backward until we reach a space.

This simulates maximal fitting per row.

At the end, the total number of complete sentence repetitions is:

position // len(s)

because every full cycle through s represents one complete sentence.

Algorithm

1. Join the sentence into:

s = " ".join(sentence) + " "

2. Let:

position = 0

3. For each row:
   • Add cols to position.
   • If s[position % len(s)] is a space:
     • Move forward one more character.
   • Otherwise:
     • Move backward until the previous character is a space.
4. Return:

position // len(s)

Correctness

The string:

s = " ".join(sentence) + " "

contains exactly one complete sentence followed by a trailing separator space.

The variable position tracks how many characters of the infinite repeated sentence stream have been consumed by the screen.

For each row, adding cols greedily attempts to place as many characters as possible.

If the landing position is a space, then the row ended exactly at a word boundary, so the next row can start immediately after that space.

If the landing position is inside a word, words are not allowed to split across rows. The algorithm moves backward until it reaches the nearest valid word boundary.

Thus each row contains the maximum valid prefix that fits within cols characters.

After all rows are processed, every complete traversal of s corresponds to one complete sentence placement.

Therefore:

position // len(s)

is exactly the number of complete sentence repetitions that fit on the screen.

Complexity

Here:

In practice, the backward adjustment is amortized efficient because the pointer never repeatedly scans long distances overall.

Implementation

from typing import List

class Solution:
    def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:
        s = " ".join(sentence) + " "
        n = len(s)

        position = 0

        for _ in range(rows):
            position += cols

            if s[position % n] == " ":
                position += 1
            else:
                while position > 0 and s[(position - 1) % n] != " ":
                    position -= 1

        return position // n

Code Explanation

We first build one cyclic sentence string:

s = " ".join(sentence) + " "

For:

["hello", "world"]

this becomes:

"hello world "

The trailing space is important because it cleanly separates sentence repetitions.

We store the length:

n = len(s)

The variable:

position

tracks how many characters have been consumed from the infinite repeated sentence.

For each row:

position += cols

greedily fills the row.

If we land exactly on a space:

if s[position % n] == " ":

then the next row can begin immediately after that space:

position += 1

Otherwise, we landed in the middle of a word.

Since words cannot split across rows, we move backward:

while position > 0 and s[(position - 1) % n] != " ":
    position -= 1

until we reach the previous space.

Finally:

return position // n

counts how many complete sentence cycles were consumed.

Alternative DP Optimization

When rows is very large, we can precompute row transitions.

For each possible starting word index:

Then each row becomes an O(1) lookup.

This optimization reduces repeated scanning when many rows begin with the same word.

Testing

def test_words_typing():
    s = Solution()

    assert s.wordsTyping(["hello", "world"], 2, 8) == 1

    assert s.wordsTyping(["a", "bcd", "e"], 3, 6) == 2

    assert s.wordsTyping(["i", "had", "apple", "pie"], 4, 5) == 1

    assert s.wordsTyping(["a"], 3, 1) == 3

    assert s.wordsTyping(["abc"], 2, 2) == 0

    assert s.wordsTyping(["a", "b"], 1, 3) == 1

    assert s.wordsTyping(["longword"], 2, 8) == 2

    print("all tests passed")

Test Notes