# Count The Repetitions
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-the-repetitions)
Canonical: https://scaleengineer.com/dsa/problems/count-the-repetitions
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
---
## 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 = "ab**dbe**c"` 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`.

**Example 1:**

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

**Example 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 <= 106`

# Approaches
## Brute-force Simulation
This approach directly simulates the process described in the problem. We can think of `str1` as `s1` concatenated `n1` times. We then iterate through this conceptual large string, character by character, trying to form as many non-overlapping subsequences of `s2` as possible. We maintain a count of how many times `s2` has been fully formed. Since `n1` can be very large, we don't build the full `str1` string in memory. Instead, we use nested loops: an outer loop that runs `n1` times (for each `s1` block) and an inner loop that iterates through the characters of `s1`.
**Time:** O(n1 * s1.length). We have a loop that runs `n1` times, and inside it, another loop runs `s1.length` times. Given `n1` can be up to 10^6 and `s1.length` up to 100, this can be up to 10^8 operations, which is too slow. · **Space:** O(1), as we only use a few variables to keep track of the counts and indices.
**Pros:** Simple to understand and implement.; Low memory usage.
**Cons:** The time complexity is too high for the given constraints on `n1` and `s1.length`, leading to a Time Limit Exceeded (TLE) error on most platforms.
### Explanation
The brute-force method involves a straightforward simulation. We need to find how many times `s2` can be formed as a subsequence from `s1` repeated `n1` times. We can maintain a pointer, `s2_idx`, for the current character we are searching for in `s2`, and a counter, `s2_count`, for the number of times we have successfully formed `s2`.

We iterate `n1` times, and in each iteration, we scan through `s1`. During the scan, if we find a character that matches `s2.charAt(s2_idx)`, we advance the pointer `s2_idx`. When `s2_idx` reaches the end of `s2`, it signifies that one instance of `s2` has been completed. We then increment `s2_count` and reset `s2_idx` to 0 to begin the search for the next instance of `s2`.

After iterating through all `n1` blocks of `s1`, `s2_count` will give us the total number of `s2` repetitions. The final answer `m` is `s2_count / n2`.

```java
class Solution {
    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        long s2_count = 0;
        int s2_idx = 0;
        int s1_len = s1.length();
        int s2_len = s2.length();

        for (int i = 0; i < n1; i++) {
            for (int j = 0; j < s1_len; j++) {
                if (s1.charAt(j) == s2.charAt(s2_idx)) {
                    s2_idx++;
                    if (s2_idx == s2_len) {
                        s2_idx = 0;
                        s2_count++;
                    }
                }
            }
        }

        return (int) (s2_count / n2);
    }
}
```
### Algorithm
- Initialize `s2_count = 0` to count the total number of `s2` repetitions found.
- Initialize `s2_idx = 0` as a pointer to the current character we are looking for in `s2`.
- Loop `n1` times, with each loop representing one concatenation of `s1`.
- Inside this loop, iterate through each character of `s1`.
- If the character from `s1` matches the character `s2.charAt(s2_idx)`, it means we found the next character of a subsequence `s2`. Increment `s2_idx`.
- If `s2_idx` becomes equal to `s2.length()`, it means we have successfully found one complete `s2` subsequence. Increment `s2_count` and reset `s2_idx` to 0 to start searching for the next `s2`.
- After the loops complete, `s2_count` holds the total number of `s2` repetitions that can be obtained from `str1 = [s1, n1]`.
- The problem asks for the maximum `m` such that `[str2, m]` can be obtained. `str2` itself consists of `n2` repetitions of `s2`. So, `[str2, m]` consists of `m * n2` repetitions of `s2`.
- The maximum `m` is therefore `s2_count / n2`.

## Optimized Simulation with Cycle Detection
The brute-force approach is inefficient because `n1` is large. We can observe that the simulation has a repeating pattern. The state of the simulation at the end of processing each `s1` block is determined by the index in `s2` (`s2_idx`) that we are currently searching for. Since there are a limited number of states (at most `s2.length()`), the sequence of states must eventually repeat, forming a cycle. By detecting this cycle, we can fast-forward the simulation instead of iterating `n1` times.
**Time:** O(s1.length * s2.length). The simulation loop runs at most `s2.length` times before a cycle is detected. Inside the loop, we iterate through `s1`, which takes `O(s1.length)`. Therefore, the complexity is dominated by the cycle detection part. · **Space:** O(s2.length). The hash maps will store at most `s2.length` entries, as this is the maximum number of unique states (`s2_idx`) before a cycle must occur.
**Pros:** Highly efficient and passes within the time limits for large inputs.; Correctly handles the large constraints by avoiding redundant computations.
**Cons:** The logic is more complex to implement correctly compared to the brute-force approach.; Requires careful handling of prefix, cycle, and suffix calculations to avoid off-by-one errors.
### Explanation
This optimized approach avoids the costly full simulation by identifying a cycle. We iterate through `s1` blocks one by one, keeping track of `s1_count`, `s2_count`, and `s2_idx`.

We use two hash maps for tracking history:
1.  `s2_idx_to_s1_count`: Maps an `s2_idx` to the `s1_count` when that `s2_idx` was first encountered at the start of an `s1` block.
2.  `s1_count_to_s2_count`: Maps an `s1_count` to the total `s2_count` accumulated after processing that many `s1` blocks.

As we iterate, before processing the `s1_i`-th block, we check if the current `s2_idx` is already in `s2_idx_to_s1_count`. If it is, a cycle is detected.

- **Prefix**: The part of the simulation before the cycle starts. Its length is `prev_s1_i` blocks, and it yields `prev_s2_count` repetitions of `s2`.
- **Cycle**: The repeating part. Its length in `s1` blocks and the number of `s2`s it produces can be calculated from the stored history.

Once the cycle is found, we can calculate the total `s2` count without further simulation:
`total_s2s = (prefix_s2s) + (num_cycles * cycle_s2s) + (suffix_s2s)`

The number of cycles is determined by how many times the cycle pattern fits into the remaining `s1` blocks. The suffix count is found by looking up the history for the small number of remaining blocks.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        // Map to detect cycle: s2_idx -> s1_count
        Map<Integer, Integer> s2_idx_to_s1_count = new HashMap<>();
        // History of s2 counts: s1_count -> s2_count
        Map<Integer, Integer> s1_count_to_s2_count = new HashMap<>();
        
        int s2_idx = 0;
        int s2_count = 0;
        
        for (int s1_i = 0; s1_i < n1; s1_i++) {
            // Check for cycle start
            if (s2_idx_to_s1_count.containsKey(s2_idx)) {
                // Cycle detected
                int prev_s1_i = s2_idx_to_s1_count.get(s2_idx);
                int prev_s2_count = s1_count_to_s2_count.get(prev_s1_i);
                
                // Cycle pattern
                int cycle_s1_len = s1_i - prev_s1_i;
                int cycle_s2_count = s2_count - prev_s2_count;
                
                // Calculate total s2's using the cycle pattern
                long remaining_s1_after_prefix = n1 - prev_s1_i;
                long num_cycles = remaining_s1_after_prefix / cycle_s1_len;
                
                long total_s2 = (long)prev_s2_count + num_cycles * cycle_s2_count;
                
                // Suffix part
                long suffix_s1_len = remaining_s1_after_prefix % cycle_s1_len;
                int suffix_s1_end_count = prev_s1_i + (int)suffix_s1_len;
                int suffix_s2_count = s1_count_to_s2_count.get(suffix_s1_end_count) - prev_s2_count;
                
                total_s2 += suffix_s2_count;
                
                return (int) (total_s2 / n2);
            }
            
            // Store history before processing the current s1 block
            s2_idx_to_s1_count.put(s2_idx, s1_i);
            s1_count_to_s2_count.put(s1_i, s2_count);
            
            // Simulate one block of s1
            for (int j = 0; j < s1.length(); j++) {
                if (s1.charAt(j) == s2.charAt(s2_idx)) {
                    s2_idx++;
                    if (s2_idx == s2.length()) {
                        s2_idx = 0;
                        s2_count++;
                    }
                }
            }
        }
        
        // No cycle found within n1 blocks (n1 was small)
        return s2_count / n2;
    }
}
```
### Algorithm
- The state of our simulation after processing a block of `s1` can be uniquely identified by `s2_idx`, the index of the character we are currently searching for in `s2`.
- Since `s2_idx` can only have `s2.length()` different values (0 to `s2.length()-1`), the state must eventually repeat.
- When a state `s2_idx` repeats, we have found a cycle. The simulation from this point onwards will repeat the same pattern of `s2` counts and `s2_idx` transitions.
- We can use a hash map to detect this cycle. The map, say `recall`, will store the `s1_count` and `s2_count` at the moment a particular `s2_idx` is first seen.
- We simulate block by block. Before processing a block, we check if the current `s2_idx` is in our `recall` map.
- If it is, we have found a cycle. We can calculate:
    1. The `prefix`: the number of `s1` blocks and `s2` counts before the cycle began.
    2. The `cycle`: the number of `s1` blocks and `s2` counts in one full cycle.
- With this information, we can calculate how many full cycles fit in the remaining `n1` blocks and add the corresponding `s2` counts.
- Finally, we calculate the `s2` counts for the `suffix` (the remaining blocks that don't form a full cycle) and add them to the total.
- The total `s2` count is the sum from the prefix, the full cycles, and the suffix. The final answer is this total divided by `n2`.

# Solutions
### Java

```java
class Solution {
public
  int getMaxRepetitions(String s1, int n1, String s2, int n2) {
    int m = s1.length(), n = s2.length();
    int[][] d = new int[n][0];
    for (int i = 0; i < n; ++i) {
      int j = i;
      int cnt = 0;
      for (int k = 0; k < m; ++k) {
        if (s1.charAt(k) == s2.charAt(j)) {
          if (++j == n) {
            j = 0;
            ++cnt;
          }
        }
      }
      d[i] = new int[]{cnt, j};
    }
    int ans = 0;
    for (int j = 0; n1 > 0; --n1) {
      ans += d[j][0];
      j = d[j][1];
    }
    return ans / n2;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int getMaxRepetitions(string s1, int n1, string s2, int n2) {
    int m = s1.size(), n = s2.size();
    vector<pair<int, int>> d;
    for (int i = 0; i < n; ++i) {
      int j = i;
      int cnt = 0;
      for (int k = 0; k < m; ++k) {
        if (s1[k] == s2[j]) {
          if (++j == n) {
            ++cnt;
            j = 0;
          }
        }
      }
      d.emplace_back(cnt, j);
    }
    int ans = 0;
    for (int j = 0; n1; --n1) {
      ans += d[j].first;
      j = d[j].second;
    }
    return ans / n2;
  }
};

```

### Python

```python
class Solution:
    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int: n = len(s2) d = {} for i in range(n): cnt = 0 j = i for c in s1: if c == s2[j]: j += 1 if j == n: cnt += 1 j = 0 d[i] = (cnt, j) ans = 0 j = 0 for _ in range(n1): cnt, j = d[j] ans += cnt return ans // n2

```