Maximum Repeating Substring - Solution & Explanation
Problem Statement
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 <= 1001 <= word.length <= 100sequenceandwordcontains only lowercase English letters.
Approach Overview
Problem Overview: You are given two strings: sequence and word. The goal is to find the maximum integer k such that word repeated k times (i.e., word * k) appears as a substring of sequence. The challenge is efficiently checking how many times the pattern can repeat consecutively while still remaining inside the larger string.
Approach 1: Brute Force Repetition Check (Time: O(n * m * k), Space: O(1))
The direct strategy repeatedly build the string word * k and check whether it exists inside sequence. Start with k = 1, concatenate word each time, and run a substring search using built-in string matching. Stop when the constructed string is no longer found in sequence. The last valid k is the answer. This approach relies heavily on repeated substring checks and string concatenation, so performance degrades when the sequence becomes large. Still, it is simple to implement and demonstrates a clear understanding of the problem mechanics. The logic mainly involves standard operations from string manipulation and basic substring search.
Approach 2: Binary Search on Repetition Count (Time: O(n log k), Space: O(1))
A more efficient solution treats the answer k as a search space. Instead of checking every repetition count sequentially, apply binary search between 0 and n / m (maximum possible repetitions). For each mid value, construct word repeated mid times and check whether it exists in sequence. If the substring exists, move the search right to test larger values. Otherwise move left. This reduces the number of substring checks from linear to logarithmic. The key insight is that the condition is monotonic: if word * k exists, then all smaller repetitions must also exist. This technique combines ideas from string matching and search optimization to significantly reduce unnecessary checks.
Another way to reason about the problem is through pattern repetition tracking similar to techniques used in dynamic programming string problems. Instead of exploring every substring combination, the algorithm focuses only on valid repetition lengths derived from the pattern itself.
Recommended for interviews: Start by explaining the brute force approach because it clearly models the definition of repeated substrings. Then move to the binary search optimization. Interviewers usually expect you to recognize that the answer space is bounded and monotonic, making binary search a clean improvement. Demonstrating both approaches shows problem understanding first and algorithmic optimization second.
Approach 1: Brute Force Approach
In this approach, we incrementally increase the count k and form the concatenated string consisting of word repeated k times. We then check if the resulting string is a substring of sequence. The maximum value of k for which this is true is the result.
The function maxRepeating checks substrings of sequence generated by repeating word. We use strcat to concatenate word to itself and strstr to check if it is a substring of sequence.
Complexity
Time Complexity: O((n + m) * l), where n is the length of sequence, m is the length of word, and l is the maximum value of k.
Space Complexity: O(k * m) due to the storage of the repeated string.
Approach 2: Optimized Approach Using Binary Search
This approach uses binary search to determine the maximum k at which word repeated k times is a substring of sequence. The binary search is applied over possible values of k, ensuring a more efficient search compared to linear testing of each k.
This C solution uses binary search to iterate over the number of repetitions, concatenating word accordingly and using strstr for the substring search within sequence.
Complexity
Time Complexity: O((n + m) * log(n/m))
Space Complexity: O(k * m)
Approach 3: Default Approach
Try this approach in the editor βComplexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O((n + m) * l), where Space Complexity: O(k * m) due to the storage of the repeated string. |
| Optimized Approach Using Binary Search | Time Complexity: O((n + m) * log(n/m)) Space Complexity: O(k * m) |
| Default Approach | β |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Repetition Check | O(n * m * k) | O(1) | Best for understanding the problem quickly or when constraints are small. |
| Binary Search on Repetition Count | O(n log k) | O(1) | Preferred for interviews and larger inputs since it reduces repeated substring checks. |
Video Solution
1668. Maximum Repeating Substring (Leetcode Easy) β’ Programming Live with Larry β’ 3,060 views views
Watch 9 more video solutions βFrequently Asked Questions
Is Maximum Repeating Substring easy or hard?
How to solve Maximum Repeating Substring in O(n)?
Maximum Repeating Substring Python or Java solution?
What is the best approach for Maximum Repeating Substring?
Is Maximum Repeating Substring asked at Google/Amazon/Meta?
What data structure is used in Maximum Repeating Substring?
What is the time complexity of Maximum Repeating Substring?
Ready to solve this problem?
Practice Maximum Repeating Substring with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor