Problem Description

Given two strings, sequence and word, you are to find the maximum number k such that word repeated k times is a substring of sequence. In other words, you want to find the largest k for which the string word + word + ... + word (repeated k times) can be found as a contiguous substring within sequence.

• Only one valid solution exists for each input.
• Do not reuse or overlap substrings when counting repeats.
• The answer is 0 if word does not appear at all as a substring.
• Both sequence and word consist of lowercase English letters.

Example:
If sequence = "ababcababcababc" and word = "ababc", then the answer is 3 because "ababcababcababc" is "ababc" repeated 3 times.

Thought Process

At first glance, the problem seems to ask for the longest contiguous run of word inside sequence. A brute-force approach would be to check, for every possible starting position in sequence, how many times word repeats consecutively. This would mean, for each index, repeatedly checking substrings of length len(word) to see if they match word, and counting how many times this happens in a row.

However, this approach can be inefficient, especially for long strings. To optimize, we can look for patterns or use string searching in a smarter way. For example, we can try to "slide" through sequence and, whenever we see word starting at a position, count how many times it repeats from there. We also realize that overlapping is not allowed, so after counting a run, we can skip ahead.

The key insight is that we only care about the maximum number of consecutive (non-overlapping) repeats anywhere in the string, not the total number of repeats.

Solution Approach

Let's break down the efficient solution step by step:

1. Initialize a variable (e.g., max_repeat) to keep track of the maximum number of consecutive repeats found.
2. Iterate through each position in sequence from 0 to len(sequence) - len(word).
3. At each position, check for consecutive repeats:
   • Set a counter count = 0.
   • While the substring starting at the current position and of length len(word) matches word, increment count and move the position forward by len(word).
   • Compare count with max_repeat and update if needed.
4. Return the maximum repeat count found.

This approach ensures that we check every possible starting point only once and always move forward by the length of word when consecutive matches are found. We use simple string slicing and comparison, which is efficient for this problem size.

Example Walkthrough

Let's use the following example:

• sequence = "aaabaaaabaaabaaaabaaaabaaa"
• word = "aaab"

We want to find the maximum k such that "aaab" repeated k times is a substring of sequence.

1. Start at position 0: sequence[0:4] = "aaab" matches word, so count = 1.
   • Next, sequence[4:8] = "aaaa" does not match, so stop here.
   • Update max_repeat = 1.
2. Move to position 5: sequence[5:9] = "aaab" matches, count = 1.
   • Next, sequence[9:13] = "aaab" matches again, count = 2.
   • Next, sequence[13:17] = "aaab" matches again, count = 3.
   • Next, sequence[17:21] = "aaab" matches again, count = 4.
   • Next, sequence[21:25] = "aaa" (too short), so stop.
   • Update max_repeat = 4.
3. Continue this process for all positions. The maximum found is 4.

Thus, the answer is 4.

Code Implementation

class Solution:
    def maxRepeating(self, sequence: str, word: str) -> int:
        max_repeat = 0
        n, m = len(sequence), len(word)
        for i in range(n - m + 1):
            count = 0
            while sequence[i + count * m : i + (count + 1) * m] == word:
                count += 1
            max_repeat = max(max_repeat, count)
        return max_repeat
      

class Solution {
public:
    int maxRepeating(string sequence, string word) {
        int max_repeat = 0;
        int n = sequence.size(), m = word.size();
        for (int i = 0; i <= n - m; ++i) {
            int count = 0;
            while (i + (count + 1) * m <= n && 
                   sequence.substr(i + count * m, m) == word) {
                count++;
            }
            max_repeat = max(max_repeat, count);
        }
        return max_repeat;
    }
};
      

class Solution {
    public int maxRepeating(String sequence, String word) {
        int maxRepeat = 0;
        int n = sequence.length(), m = word.length();
        for (int i = 0; i <= n - m; ++i) {
            int count = 0;
            while (i + (count + 1) * m <= n &&
                   sequence.substring(i + count * m, i + (count + 1) * m).equals(word)) {
                count++;
            }
            maxRepeat = Math.max(maxRepeat, count);
        }
        return maxRepeat;
    }
}
      

var maxRepeating = function(sequence, word) {
    let maxRepeat = 0;
    const n = sequence.length, m = word.length;
    for (let i = 0; i <= n - m; ++i) {
        let count = 0;
        while (sequence.substr(i + count * m, m) === word) {
            count++;
        }
        maxRepeat = Math.max(maxRepeat, count);
    }
    return maxRepeat;
};
      

Time and Space Complexity

Brute-force Approach:
For every index in sequence, you could potentially check all possible substring lengths, resulting in a time complexity of O(N^2), where N is the length of sequence.

Optimized Approach (as above):
For each starting index, we only check as many times as word can repeat consecutively. In the worst case, for each index, we might scan up to N/M repeats, but in practice, this is much faster because the inner loop only runs when matches are found. Thus, the worst-case time complexity is O(N * K), where K is the maximum number of repeats, but typically it's much less.

Space Complexity:
The solution uses only a constant amount of extra space: O(1).

Summary

The key to solving the Maximum Repeating Substring problem is to efficiently scan for the longest contiguous run of the word within sequence. By checking each possible start position and counting consecutive, non-overlapping repeats, we avoid unnecessary work and keep the solution simple and efficient. This method is easy to implement, requires minimal extra space, and leverages basic string operations to achieve the goal.