# Maximum Repeating Substring
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-repeating-substring)
Canonical: https://scaleengineer.com/dsa/problems/maximum-repeating-substring
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [String Matching](https://scaleengineer.com/dsa/patterns/string-matching)
**Data structures:** String
**Companies:** [Turing](https://scaleengineer.com/companies/turing), [Pure Storage](https://scaleengineer.com/companies/pure-storage), [Asana](https://scaleengineer.com/companies/asana)
---
## Problem
For a string `sequence`, a string `word` is **`k`\-repeating** if `word` concatenated `k` times is a substring of `sequence`. The `word`'s **maximum `k`\-repeating value** is the highest value `k` where `word` is `k`\-repeating in `sequence`. If `word` is not a substring of `sequence`, `word`'s maximum `k`\-repeating value is `0`.

Given strings `sequence` and `word`, return _the **maximum `k`\-repeating value** of `word` in `sequence`_.

**Example 1:**

**Input:** sequence = "ababc", word = "ab"
**Output:** 2
**Explanation:** "abab" is a substring in "ababc".

**Example 2:**

**Input:** sequence = "ababc", word = "ba"
**Output:** 1
**Explanation:** "ba" is a substring in "ababc". "baba" is not a substring in "ababc".

**Example 3:**

**Input:** sequence = "ababc", word = "ac"
**Output:** 0
**Explanation:** "ac" is not a substring in "ababc". 

**Constraints:**

* `1 <= sequence.length <= 100`
* `1 <= word.length <= 100`
* `sequence` and `word` contains only lowercase English letters.

# Approaches
## Brute-force by Building and Checking
This approach iteratively builds a repeating string from `word` and checks if it's a substring of `sequence`. We start with `k=1` (just `word` itself), then `k=2` (`word` + `word`), and so on. We continue this process as long as the generated string is found within `sequence`. The maximum `k` for which this holds true is our answer.
**Time:** O(N^3 / M), where N is the length of `sequence` and M is the length of `word`. The loop runs at most `N/M` times. In iteration `k`, `sequence.contains()` on a pattern of length `k*M` takes `O(N * k*M)` time. Summing this over all `k` gives a high polynomial complexity. · **Space:** O(N), where N is the length of `sequence`. The `StringBuilder` can grow up to a length proportional to N.
**Pros:** Very simple to conceptualize and write.; Leverages built-in string methods effectively.
**Cons:** Inefficient due to repeated searching of increasingly larger strings.; String concatenation in a loop can be slow if not handled properly (e.g., with `StringBuilder`).; The time complexity is high for the given constraints, although it passes due to the small size of inputs.
### Explanation
We initialize a counter `k` to 0 and a `StringBuilder` `repeatedWord` with the initial `word`. We then enter a loop. In each iteration, we check if the current `repeatedWord` is a substring of `sequence` using the `contains()` method. If it is, we increment our answer `k` and append another `word` to `repeatedWord` for the next iteration. If it's not, we know that no longer repetition will be a substring either, so we can stop and return the current value of `k`. The maximum possible `k` is `sequence.length() / word.length()`, which provides a natural bound for the loop.

```java
class Solution {
    public int maxRepeating(String sequence, String word) {
        int k = 0;
        StringBuilder repeatedWord = new StringBuilder(word);
        while (sequence.contains(repeatedWord.toString())) {
            k++;
            repeatedWord.append(word);
        }
        return k;
    }
}
```
### Algorithm
- 1. Initialize a counter `k` to 0.
- 2. Create a `StringBuilder` named `sb` and initialize it with `word`.
- 3. Start a `while` loop that continues as long as `sequence.contains(sb.toString())` is true.
- 4. Inside the loop, increment `k`.
- 5. Append `word` to `sb` to check for the next level of repetition.
- 6. After the loop terminates, return `k`.

## Iterating Through Sequence
Instead of building the search string, this approach iterates through all possible starting positions in the `sequence`. For each position, it checks how many times `word` can be consecutively repeated starting from there. The overall maximum count found across all starting positions is the answer.
**Time:** O(N^2), where N is the length of `sequence`. The outer loop runs `O(N)` times. The inner loop can run up to `O(N/M)` times, and each check inside takes `O(M)`. This results in a total time of `O(N * (N/M) * M) = O(N^2)`. · **Space:** O(M), where M is the length of `word`. The space is used to store the substring created for comparison.
**Pros:** More efficient than the first approach.; Avoids creating very large strings for searching.
**Cons:** The nested loop structure leads to a quadratic time complexity, which can be improved.
### Explanation
We initialize a variable `maxK` to store the maximum repetitions found so far, setting it to 0. We loop through the `sequence` with an index `i` from 0 up to `sequence.length() - word.length()`. This `i` represents a potential starting point of a repeating block. For each `i`, we start a nested loop to count how many times `word` repeats consecutively. We use a pointer `j` starting at `i` and advance it by `word.length()` as long as the substring of `sequence` at `j` matches `word`. We keep a `currentK` for the count starting at `i` and update `maxK` with the maximum `currentK` found. After checking all starting positions, `maxK` will hold the final answer.

```java
class Solution {
    public int maxRepeating(String sequence, String word) {
        int n = sequence.length();
        int m = word.length();
        int maxK = 0;
        for (int i = 0; i <= n - m; i++) {
            int currentK = 0;
            for (int j = i; j <= n - m; j += m) {
                String sub = sequence.substring(j, j + m);
                if (sub.equals(word)) {
                    currentK++;
                } else {
                    break; // The repetition is broken
                }
            }
            maxK = Math.max(maxK, currentK);
        }
        return maxK;
    }
}
```
### Algorithm
- 1. Initialize `maxK = 0`. Let `n` be the length of `sequence` and `m` be the length of `word`.
- 2. Loop with an index `i` from `0` to `n - m`.
- 3. Inside the loop, initialize `currentK = 0`.
- 4. Start a nested loop with index `j` starting from `i`, incrementing by `m` in each step, as long as `j <= n - m`.
- 5. Check if `sequence.substring(j, j + m)` equals `word`.
- 6. If they are equal, increment `currentK`.
- 7. If they are not equal, break the inner loop.
- 8. After the inner loop, update `maxK = Math.max(maxK, currentK)`.
- 9. After the outer loop, return `maxK`.

## Dynamic Programming
This is the most efficient approach among the three. We use a dynamic programming array, `dp`, where `dp[i]` stores the maximum number of times `word` repeats consecutively, ending exactly at index `i-1` of the `sequence`. By iterating through the `sequence` and building up this `dp` array, we can find the solution in a single pass.
**Time:** O(N * M), where N is `sequence.length()` and M is `word.length()`. We iterate through the `sequence` once (O(N)). In each step, we perform a substring operation and a string comparison, which takes O(M) time. · **Space:** O(N), where N is the length of `sequence`. We use an auxiliary DP array of size N+1.
**Pros:** Most efficient time complexity among the presented solutions.; Solves the problem in a single pass over the sequence.
**Cons:** Requires O(N) extra space, which might be a concern for very large inputs (though not with the given constraints).; The DP state transition might be slightly less intuitive than direct iteration.
### Explanation
We create a DP array `dp` of size `n + 1`, where `n` is the length of `sequence`. `dp[i]` will represent the number of consecutive repetitions of `word` ending at `sequence[i-1]`. We iterate from `i = 1` to `n`. For each `i`, we check if the substring `sequence.substring(i - m, i)` (where `m` is `word.length()`) is equal to `word`. If it matches, it means we have found an occurrence of `word`. This occurrence could be a continuation of a previous repeating block that ended at index `i - m`. The count for that is stored in `dp[i - m]`. Therefore, if there's a match, we set `dp[i] = dp[i - m] + 1`. The final answer is the maximum value found anywhere in the `dp` array, because the maximum repeating substring can end at any position.

```java
class Solution {
    public int maxRepeating(String sequence, String word) {
        int n = sequence.length();
        int m = word.length();
        if (n < m) {
            return 0;
        }
        
        int[] dp = new int[n + 1];
        int maxK = 0;
        
        for (int i = m; i <= n; i++) {
            String sub = sequence.substring(i - m, i);
            if (sub.equals(word)) {
                dp[i] = dp[i - m] + 1;
            }
            maxK = Math.max(maxK, dp[i]);
        }
        
        return maxK;
    }
}
```
### Algorithm
- 1. Initialize a DP array `dp` of size `sequence.length() + 1` with all zeros.
- 2. Initialize `maxK = 0`.
- 3. Iterate with `i` from `word.length()` to `sequence.length()`.
- 4. In each iteration, extract the substring of `sequence` of length `word.length()` ending at index `i-1`. This is `sequence.substring(i - word.length(), i)`.
- 5. If this substring equals `word`, it means we have a valid repetition. The number of repetitions is 1 plus the number of repetitions that ended just before this `word` started, which is at index `i - word.length()`. So, we set `dp[i] = dp[i - word.length()] + 1`.
- 6. Update `maxK = Math.max(maxK, dp[i])` in each iteration.
- 7. After the loop, return `maxK`.

# Solutions
### Java

```java
class Solution { public int maxRepeating ( String sequence , String word ) { for ( int k = sequence . length () / word . length (); k > 0 ; -- k ) { if ( sequence . contains ( word . repeat ( k ))) { return k ; } } return 0 ; } }
```

### CPP

```cpp
class Solution { public: int maxRepeating ( string sequence , string word ) { int ans = 0 ; string t = word ; int x = sequence . size () / word . size (); for ( int k = 1 ; k <= x ; ++ k ) { // C++ 这里从小到大枚举重复值 if ( sequence . find ( t ) != string :: npos ) { ans = k ; } t += word ; } return ans ; } };
```

### Python

```python
class Solution : def maxRepeating ( self , sequence : str , word : str ) -> int : for k in range ( len ( sequence ) // len ( word ), - 1 , - 1 ): if word * k in sequence : return k
```