466. Count The Repetitions
Documentation: "Count The Repetitions"Table of Contents
Problem Statement
Intuition
Key Observations
Approach
Edge Cases
Complexity Analysis

Time Complexity
Sp
# **Documentation: "Count The Repetitions"**

## **Table of Contents**
1. [Problem Statement](#1-problem-statement)
2. [Intuition](#2-intuition)
3. [Key Observations](#3-key-observations)
4. [Approach](#4-approach)
5. [Edge Cases](#5-edge-cases)
6. [Complexity Analysis](#6-complexity-analysis)
   - [Time Complexity](#time-complexity)
   - [Space Complexity](#space-complexity)
7. [Alternative Approaches](#7-alternative-approaches)
8. [Code Implementation](#8-code-implementation)
9. [Test Cases](#9-test-cases)
10. [Final Thoughts](#10-final-thoughts)

---

## **1. Problem Statement**

Given two strings `s1` and `s2`, and two integers `n1` and `n2`, define the following:

- `str1 = s1 * n1` is the string formed by concatenating `s1` `n1` times.
- `str2 = s2 * n2` is the string formed by concatenating `s2` `n2` times.

The problem asks to determine the maximum integer `m` such that we can obtain `str2` (which is `s2 * m`) from `str1` (which is `s1 * n1`), meaning `s2` can be formed from `s1` with repeated occurrences.

---

## **2. Intuition**

The intuition behind solving this problem efficiently is based on **pattern matching**. We need to simulate how `s2` can be formed by skipping some characters of `s1`. Given that `n1` and `n2` can be very large (up to 10^6), we cannot afford to directly construct `s1 * n1` or `s2 * n2` due to memory constraints.

Instead, we aim to simulate the process of forming `s2` from `s1` while maintaining the count of how many times we can form `s2` in one iteration of `s1`. By detecting **cycles** in this process, we can jump over multiple iterations of `s1` without recalculating the entire process from scratch.

---

## **3. Key Observations**

1. **Subsequence Property**: We need to check if `s2` is a subsequence of repeated `s1`. A subsequence means that the characters of `s2` appear in `s1` in the same order, but not necessarily consecutively.
   
2. **Pattern Repetition**: After processing one complete repeat of `s1`, the process can repeat itself, and this forms a cycle. By detecting this cycle, we can use it to skip forward, optimizing the solution.

3. **Cycle Detection**: The cycle can be identified when the same state (position in `s2`) occurs again after processing some portion of `s1`. Once we detect the cycle, we can compute how many full cycles fit into the remaining repetitions of `s1`.

---

## **4. Approach**

### **Step-by-step Approach**:

1. **Initial Setup**: 
   - We start by initializing variables to track the number of times `s2` has been matched and the current position in `s2`.
   - Use a dictionary `recall` to store the positions and count of matched `s2` for cycle detection.

2. **Iterate over `s1`**:
   - For each character in `s1`, check if it matches the current character in `s2`. If it does, increment the position in `s2`.
   - When we match all characters in `s2`, reset the `s2` index and increment the counter for complete `s2` matches.

3. **Cycle Detection**:
   - After processing each `s1` repeat, check if the position in `s2` has been encountered before.
   - If it has, a cycle has been detected. Calculate how many full cycles can fit into the remaining iterations of `s1`, and skip to that position.

4. **Calculate the Result**:
   - The result is the total number of full `s2` matches divided by `n2`, which represents the maximum number of `s2` substrings that can be formed from the given `str1`.

---

## **5. Edge Cases**

1. **Empty or Short Strings**: 
   - If `s1` or `s2` is very short or empty, the cycle detection mechanism ensures that we handle it gracefully.
   
2. **No Possible Match**: 
   - If `s2` cannot be formed from `s1` at all, the result should be 0.

3. **Small Repetitions**:
   - For small values of `n1` and `n2`, the algorithm will handle these cases without hitting performance bottlenecks due to the efficient cycle detection.

---

## **6. Complexity Analysis**

### **Time Complexity**:

- In the worst case, we process each character of `s1` and `s2` once. Since we use cycle detection, the total number of iterations is significantly reduced when cycles are found.
  
- The time complexity can be approximated as **O(n1 + n2)**, where:
  - `n1` is the number of repetitions of `s1`.
  - `n2` is the length of `s2`.

### **Space Complexity**:

- We use a dictionary `recall` to store positions in `s2`, which takes up **O(n2)** space. Therefore, the space complexity is **O(n2)**, where `n2` is the length of `s2`.

---

## **7. Alternative Approaches**

1. **Brute-force Approach**:
   - One could attempt to concatenate `s1 * n1` and `s2 * n2`, then try to match `s2` from the concatenated string. This approach, however, would require excessive memory and would not scale well with large inputs.

2. **Greedy Approach**:
   - Another potential approach could be using a greedy algorithm, but this would still require handling the large input sizes, making cycle detection a more efficient solution.

---

## **8. Code Implementation**

```python3 []
class Solution:
    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
        if not n1:
            return 0

        s1_count = 0  # number of s1 processed
        s2_count = 0  # number of s2 matched
        index = 0     # current index in s2
        recall = dict()  # to detect cycle

        while s1_count < n1:
            for ch in s1:
                if ch == s2[index]:
                    index += 1
                    if index == len(s2):
                        s2_count += 1
                        index = 0

            s1_count += 1
            # Cycle detection
            if index in recall:
                s1_count_prev, s2_count_prev = recall[index]
                # length of the cycle
                cycle_s1 = s1_count - s1_count_prev
                cycle_s2 = s2_count - s2_count_prev

                # how many full cycles fit
                remaining_s1 = n1 - s1_count
                full_cycles = remaining_s1 // cycle_s1

                s1_count += full_cycles * cycle_s1
                s2_count += full_cycles * cycle_s2
            else:
                recall[index] = (s1_count, s2_count)

        return s2_count // n2

```

---

## **9. Test Cases**

1. **Test Case 1**:
   ```python
   s1 = "acb", n1 = 4
   s2 = "ab", n2 = 2
   output = 2
   ```
   - `str1 = acbacbacbacb`, `str2 = ababab`.
   - The maximum number of full repetitions of `s2` is 2.

2. **Test Case 2**:
   ```python
   s1 = "acb", n1 = 1
   s2 = "acb", n2 = 1
   output = 1
   ```
   - `str1 = acb`, `str2 = acb`.
   - Only 1 match is possible.

3. **Test Case 3**:
   ```python
   s1 = "a", n1 = 5
   s2 = "aa", n2 = 1
   output = 2
   ```
   - `str1 = aaaaa`, `str2 = aa`.
   - We can form `aa` twice from `str1`.

---

## **10. Final Thoughts**

This solution efficiently handles large inputs by leveraging cycle detection. By simulating the matching of `s2` in `s1` and skipping over repeated calculations, we avoid the need for constructing large strings in memory. The time complexity is reduced significantly due to this technique, making the solution scalable even for large values of `n1` and `n2`.
['Python3']