Maximum Repeating Substring
EasyPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
-
- Initialize a counter
kto 0.
- Initialize a counter
-
- Create a
StringBuildernamedsband initialize it withword.
- Create a
-
- Start a
whileloop that continues as long assequence.contains(sb.toString())is true.
- Start a
-
- Inside the loop, increment
k.
- Inside the loop, increment
-
- Append
wordtosbto check for the next level of repetition.
- Append
-
- After the loop terminates, return
k.
- After the loop terminates, return
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
-
- Initialize
maxK = 0. Letnbe the length ofsequenceandmbe the length ofword.
- Initialize
-
- Loop with an index
ifrom0ton - m.
- Loop with an index
-
- Inside the loop, initialize
currentK = 0.
- Inside the loop, initialize
-
- Start a nested loop with index
jstarting fromi, incrementing bymin each step, as long asj <= n - m.
- Start a nested loop with index
-
- Check if
sequence.substring(j, j + m)equalsword.
- Check if
-
- If they are equal, increment
currentK.
- If they are equal, increment
-
- If they are not equal, break the inner loop.
-
- After the inner loop, update
maxK = Math.max(maxK, currentK).
- After the inner loop, update
-
- After the outer loop, return
maxK.
- After the outer loop, return
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
-
- Initialize a DP array
dpof sizesequence.length() + 1with all zeros.
- Initialize a DP array
-
- Initialize
maxK = 0.
- Initialize
-
- Iterate with
ifromword.length()tosequence.length().
- Iterate with
-
- In each iteration, extract the substring of
sequenceof lengthword.length()ending at indexi-1. This issequence.substring(i - word.length(), i).
- In each iteration, extract the substring of
-
- 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 thiswordstarted, which is at indexi - word.length(). So, we setdp[i] = dp[i - word.length()] + 1.
- If this substring equals
-
- Update
maxK = Math.max(maxK, dp[i])in each iteration.
- Update
-
- After the loop, return
maxK.
- After the loop, return
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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 ; } }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 ; } };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 kVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.