> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Count The Repetitions Python Solution

> Tested Python solution for LeetCode 466 with 20 pytest cases. Generate a practice environment with lcpy.

LeetCode 466, [Hard](/catalog/hard). Topics: [Two Pointers](/catalog/topics/two-pointers), [String](/catalog/topics/string), [Dynamic Programming](/catalog/topics/dynamic-programming). [View on LeetCode](https://leetcode.com/problems/count-the-repetitions/description/).

Generate this problem as a practice environment: tested reference solution, 20 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 466   # by problem number
lcpy gen -s count_the_repetitions   # by problem name
```

## Problem

We define `str = [s, n]` as the string `str` which consists of the string `s` concatenated `n` times.

* For example, `str == ["abc", 3] =="abcabcabc"`.

We define that string `s1` can be obtained from string `s2` if we can remove some characters from `s2` such that it becomes `s1`.

* For example, `s1 = "abc"` can be obtained from `s2 = "abdbec"` based on our definition by removing the bolded underlined characters.

You are given two strings `s1` and `s2` and two integers `n1` and `n2`. You have the two strings `str1 = [s1, n1]` and `str2 = [s2, n2]`.

Return *the maximum integer* `m` *such that* `str = [str2, m]` *can be obtained from* `str1`.

### Examples

```
Input: s1 = "acb", n1 = 4, s2 = "ab", n2 = 2
Output: 2
```

```
Input: s1 = "acb", n1 = 1, s2 = "acb", n2 = 1
Output: 1
```

### Constraints

* 1 \<= s1.length, s2.length \<= 100
* s1 and s2 consist of lowercase English letters.
* 1 \<= n1, n2 \<= 10^6

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/count_the_repetitions/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/count_the_repetitions/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(len(s1) * len(s2) + len(s2))
    # Space: O(len(s2))
    def get_max_repetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
        m = len(s2)

        # For each possible starting index in s2, scan one block of s1 and
        # record the resulting index plus how many full s2 blocks were matched.
        nxt = [0] * m
        add = [0] * m
        for start in range(m):
            idx = start
            matched = 0
            for ch in s1:
                if ch == s2[idx]:
                    idx += 1
                    if idx == m:
                        idx = 0
                        matched += 1
            nxt[start] = idx
            add[start] = matched

        # Walk block by block; once a start index repeats, the remaining blocks
        # advance in a cycle whose s2-block gain per cycle is constant, so jump
        # over all full cycles at once.
        total = 0
        idx = 0
        seen: dict[int, tuple[int, int]] = {}
        block = 0
        while block < n1:
            if idx in seen:
                prev_block, prev_total = seen[idx]
                cycle_len = block - prev_block
                cycle_gain = total - prev_total
                full_cycles = (n1 - block) // cycle_len
                total += full_cycles * cycle_gain
                block += full_cycles * cycle_len
                if block == n1:
                    break
            seen[idx] = (block, total)
            total += add[idx]
            idx = nxt[idx]
            block += 1

        return total // n2
```

## Complexity

| Time | Space |
| - | - |
| O(len(s1) \* len(s2) + len(s2)) | O(len(s2)) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.