# LeetCode 466: Count The Repetitions

## Problem Restatement

We are given two strings and two repetition counts:

```python
s1, n1
s2, n2
```

The notation `[s, n]` means string `s` repeated `n` times.

For example:

```python
["abc", 3] = "abcabcabc"
```

Define:

```python
str1 = [s1, n1]
str2 = [s2, n2]
```

We need to find the maximum integer `m` such that:

```python
[str2, m]
```

can be obtained from `str1` by deleting some characters.

In other words, we need to count how many full copies of `str2` can be formed as a subsequence of `str1`. The official statement defines `[s, n]` as repeated concatenation and asks for the maximum `m` such that `[str2, m]` can be obtained from `str1`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `s1`, `n1`, `s2`, `n2` |
| `str1` | `s1` repeated `n1` times |
| `str2` | `s2` repeated `n2` times |
| Output | Maximum number of full `str2` copies obtainable from `str1` |
| Matching rule | We may delete characters from `str1`, so this is subsequence matching |

Function shape:

```python
def getMaxRepetitions(s1: str, n1: int, s2: str, n2: int) -> int:
    ...
```

## Examples

Example 1:

```python
s1 = "acb"
n1 = 4
s2 = "ab"
n2 = 2
```

Then:

```python
str1 = "acbacbacbacb"
str2 = "abab"
```

From `str1`, we can form two full copies of `"abab"` as a subsequence.

Answer:

```python
2
```

Example 2:

```python
s1 = "abc"
n1 = 1
s2 = "abc"
n2 = 1
```

Then:

```python
str1 = "abc"
str2 = "abc"
```

We can form one copy.

Answer:

```python
1
```

Example 3:

```python
s1 = "abc"
n1 = 4
s2 = "ab"
n2 = 2
```

Here:

```python
str1 = "abcabcabcabc"
str2 = "abab"
```

Each two copies of `s1` can form one copy of `"abab"`.

So the answer is:

```python
2
```

## First Thought: Build the Full Strings

A direct solution is to build:

```python
full1 = s1 * n1
full2 = s2 * n2
```

Then repeatedly check how many copies of `full2` can be matched as a subsequence of `full1`.

This is easy to understand, but it fails because `n1` and `n2` can be as large as `10^6`, while each string can have length up to `100`.

So the full strings may have length up to:

```python
100 * 1_000_000 = 100_000_000
```

Building them is wasteful.

## Problem With Plain Simulation

We can simulate matching `s2` while scanning copies of `s1`.

For each copy of `s1`, scan its characters and advance an index in `s2`.

Whenever we finish one `s2`, increment a counter.

This avoids building `str1`, but it can still scan:

```python
len(s1) * n1
```

characters.

Since `len(s1) <= 100` and `n1 <= 10^6`, this may be acceptable in Python for many cases. But the cleaner solution observes that there are only `len(s2)` possible positions inside `s2`.

We can precompute what one copy of `s1` does to each possible starting position in `s2`.

## Key Insight

When scanning one full copy of `s1`, the only state we need is:

```python
index in s2 we are currently trying to match
```

Suppose this index is `j`.

After scanning one copy of `s1`, two things happen:

1. We may complete some number of full `s2` matches.
2. We end at some new index in `s2`.

So for every possible starting index `j`, precompute:

```python
record[j] = (matched_count, next_index)
```

where:

| Field | Meaning |
|---|---|
| `matched_count` | Number of full `s2` copies matched while scanning one `s1` |
| `next_index` | Position in `s2` after that scan |

Then we apply this transition `n1` times.

At the end, we have the number of full `s2` copies obtainable from `[s1, n1]`.

Since `str2 = [s2, n2]`, the answer is:

```python
full_s2_matches // n2
```

## Algorithm

First, handle impossible characters.

If `s2` contains a character that never appears in `s1`, then no copy of `s2` can be formed.

Return `0`.

Then build records.

For every starting index `start` from `0` to `len(s2) - 1`:

1. Set `j = start`.
2. Set `count = 0`.
3. Scan each character `ch` in `s1`.
4. If `ch == s2[j]`, advance `j`.
5. If `j == len(s2)`, reset `j = 0` and increment `count`.
6. Store `(count, j)`.

Then simulate `n1` copies of `s1`:

```python
matches = 0
j = 0

for _ in range(n1):
    count, j = record[j]
    matches += count
```

Return:

```python
matches // n2
```

## Walkthrough

Use:

```python
s1 = "acb"
n1 = 4
s2 = "ab"
n2 = 2
```

Possible starting indices in `s2` are:

```python
0  # waiting for 'a'
1  # waiting for 'b'
```

Start at index `0`.

Scan `"acb"`:

```python
a matches s2[0] = a, move to index 1
c does not match s2[1] = b
b matches s2[1] = b, complete one s2
```

So:

```python
record[0] = (1, 0)
```

Start at index `1`.

Scan `"acb"`:

```python
a does not match s2[1] = b
c does not match s2[1] = b
b matches s2[1] = b, complete one s2
```

So:

```python
record[1] = (1, 0)
```

Now apply four copies of `s1`.

| Copy | Start index | Full `s2` matched | Next index | Total full `s2` |
|---:|---:|---:|---:|---:|
| 1 | 0 | 1 | 0 | 1 |
| 2 | 0 | 1 | 0 | 2 |
| 3 | 0 | 1 | 0 | 3 |
| 4 | 0 | 1 | 0 | 4 |

We can form `4` copies of `s2 = "ab"`.

But `str2 = [s2, 2] = "abab"`.

So the final answer is:

```python
4 // 2 = 2
```

## Correctness

For a fixed starting index in `s2`, scanning one copy of `s1` always produces the same result: a fixed number of completed `s2` copies and a fixed next index in `s2`.

The precomputed `record` table stores exactly this transition for every possible starting index.

The full string `[s1, n1]` is made of `n1` identical copies of `s1`. Applying the corresponding transition once per copy therefore simulates the same subsequence-matching process as scanning the full repeated string directly.

The variable `matches` counts how many complete copies of `s2` can be obtained from `[s1, n1]`.

Since one copy of `str2` consists of `n2` copies of `s2`, the number of complete `str2` copies is:

```python
matches // n2
```

Therefore, the algorithm returns the required maximum repetition count.

## Complexity

Let:

```python
a = len(s1)
b = len(s2)
```

| Metric | Value | Why |
|---|---:|---|
| Time | `O(a * b + n1)` | Precompute one transition for each `s2` index, then apply `n1` transitions |
| Space | `O(b)` | Store one record per starting index in `s2` |

This avoids building either repeated string.

## Implementation

```python
class Solution:
    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
        if n1 == 0:
            return 0

        if not set(s2).issubset(set(s1)):
            return 0

        m = len(s2)
        records = []

        for start in range(m):
            count = 0
            j = start

            for ch in s1:
                if ch == s2[j]:
                    j += 1

                    if j == m:
                        count += 1
                        j = 0

            records.append((count, j))

        matches = 0
        j = 0

        for _ in range(n1):
            count, j = records[j]
            matches += count

        return matches // n2
```

## Code Explanation

First, we handle the case where no copies of `s1` exist:

```python
if n1 == 0:
    return 0
```

Then we check whether every character in `s2` appears in `s1`:

```python
if not set(s2).issubset(set(s1)):
    return 0
```

If a needed character never appears in `s1`, no complete `s2` can be formed.

The table:

```python
records = []
```

stores what happens after scanning one `s1` from each possible position in `s2`.

For each starting position:

```python
for start in range(m):
```

we scan `s1` and advance `j` whenever a character matches:

```python
if ch == s2[j]:
    j += 1
```

When `j == m`, one full `s2` has been matched:

```python
count += 1
j = 0
```

After precomputation, we apply the transition once per copy of `s1`:

```python
for _ in range(n1):
    count, j = records[j]
    matches += count
```

Finally, divide by `n2`:

```python
return matches // n2
```

because the target repeated string contains `n2` copies of `s2`.

## Faster Version With Cycle Skipping

The previous version is already efficient enough for the constraints.

We can also detect repeated states during the `n1` simulation.

A state is the current index `j` in `s2`.

If the same `j` appears again after some number of `s1` copies, then the process has entered a cycle.

```python
class Solution:
    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
        if n1 == 0:
            return 0

        if not set(s2).issubset(set(s1)):
            return 0

        index = 0
        s1_count = 0
        s2_count = 0
        seen = {}

        while s1_count < n1:
            s1_count += 1

            for ch in s1:
                if ch == s2[index]:
                    index += 1

                    if index == len(s2):
                        s2_count += 1
                        index = 0

            if index in seen:
                prev_s1_count, prev_s2_count = seen[index]

                cycle_s1 = s1_count - prev_s1_count
                cycle_s2 = s2_count - prev_s2_count

                remaining_s1 = n1 - s1_count
                cycles = remaining_s1 // cycle_s1

                s1_count += cycles * cycle_s1
                s2_count += cycles * cycle_s2
            else:
                seen[index] = (s1_count, s2_count)

        return s2_count // n2
```

The precomputed transition version is simpler and has predictable `O(len(s1) * len(s2) + n1)` complexity. The cycle-skipping version can be faster when `n1` is very large.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.getMaxRepetitions("acb", 4, "ab", 2) == 2
    assert s.getMaxRepetitions("abc", 1, "abc", 1) == 1
    assert s.getMaxRepetitions("abc", 4, "ab", 2) == 2
    assert s.getMaxRepetitions("aaa", 3, "aa", 1) == 4
    assert s.getMaxRepetitions("abc", 10, "d", 1) == 0
    assert s.getMaxRepetitions("baba", 11, "baab", 1) == 7
    assert s.getMaxRepetitions("a", 0, "a", 1) == 0

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"acb", 4, "ab", 2` | Standard example |
| `"abc", 1, "abc", 1` | Exact one-copy match |
| `"abc", 4, "ab", 2` | Repeated target grouping |
| `"aaa", 3, "aa", 1` | Dense repeated characters |
| `"abc", 10, "d", 1` | Impossible character |
| `"baba", 11, "baab", 1` | Non-trivial subsequence alignment |
| `n1 = 0` | Empty source repetition |