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 <= 100sequence and word contains only lowercase English letters.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.
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.
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.
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.
Time Complexity: O((n + m) * log(n/m))
Space Complexity: O(k * m)
| 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 | — |
| 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. |
1668. Maximum Repeating Substring (Leetcode Easy) • Programming Live with Larry • 2,912 views views
Watch 9 more video solutions →Practice Maximum Repeating Substring with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor