# LeetCode 418: Sentence Screen Fitting

## Problem Restatement

We are given:

| Value | Meaning |
|---|---|
| `sentence` | A list of words |
| `rows` | Number of screen rows |
| `cols` | Number of columns per row |

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:

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

whose answer is `1`.

The constraints include:

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

([leetcode.com](https://leetcode.com/problems/sentence-screen-fitting/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | `sentence`, `rows`, `cols` |
| Output | Number of complete sentence repetitions |
| Word rule | Words cannot split across rows |
| Space rule | One space between adjacent words |
| Order rule | Sentence order must remain unchanged |

Example function shape:

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

## Examples

Example 1:

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

The answer is:

```python
1
```

Screen layout:

```text
hello---
world---
```

The sentence fits exactly once.

Example 2:

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

The answer is:

```python
2
```

One valid layout:

```text
a-bcd-
e-a---
bcd-e-
```

The sentence repeats twice completely.

Example 3:

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

The answer is:

```python
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:

```python
s = "hello world "
```

Notice the trailing space.

Now the sentence behaves like an infinite repeating string:

```text
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:

```python
position // len(s)
```

because every full cycle through `s` represents one complete sentence.

## Algorithm

1. Join the sentence into:

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

2. Let:

```python
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:

```python
position // len(s)
```

## Correctness

The string:

```python
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:

```python
position // len(s)
```

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

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(rows + total_backtracking)` | Each row advances once |
| Space | `O(L)` | We store the joined sentence string |

Here:

| Symbol | Meaning |
|---|---|
| `L` | Length of the joined sentence string |

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

## Implementation

```python
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:

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

For:

```python
["hello", "world"]
```

this becomes:

```python
"hello world "
```

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

We store the length:

```python
n = len(s)
```

The variable:

```python
position
```

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

For each row:

```python
position += cols
```

greedily fills the row.

If we land exactly on a space:

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

then the next row can begin immediately after that space:

```python
position += 1
```

Otherwise, we landed in the middle of a word.

Since words cannot split across rows, we move backward:

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

until we reach the previous space.

Finally:

```python
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:

| Value | Meaning |
|---|---|
| Next starting word index after one row |
| Number of completed sentence cycles in that row |

Then each row becomes an `O(1)` lookup.

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

## Testing

```python
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

| Test | Why |
|---|---|
| Standard example 1 | Exact row fitting |
| Standard example 2 | Multiple sentence repetitions |
| Standard example 3 | Mixed word lengths |
| Single short word | Repeated many times |
| Word longer than row | Cannot fit |
| Exact fit with space | Boundary handling |
| Word length equals columns | Full-row single word |