Maximum Repeating Substring — Solution in Python, Java & C++
Maximum Repeating Substring solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on strings.
Maximum Repeating Substring is an easy coding problem on strings, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Strings
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
For a string word and an integer k, word has k-repeating value in sequence if word concatenated k times is a substring of sequence.
Return the maximum such k, or 0 if word is not a substring of sequence at all.
Example 1
Input: sequence = "ababc", word = "ab"
Output: 2
Explanation: "abab" occurs; "ababab" does not.
Example 2
Input: sequence = "ababc", word = "ba"
Output: 1
Example 3
Input: sequence = "ababc", word = "ac"
Output: 0
Constraints
1 <= sequence.length <= 1001 <= word.length <= 100Both strings consist of lowercase English letters.
Hints for Maximum Repeating Substring
Hint 1
The answer is bounded by
sequence.length / word.length.Hint 2
Try
k = 1, 2, 3, …and stop when the repeated word no longer occurs.Hint 3
Building the repeated string and using a plain substring search is fast enough here.
How to solve Maximum Repeating Substring
The property is monotone: if word repeated k times occurs, so does word repeated k-1 times. So climbing k from 1 and stopping at the first failure finds the maximum.
Approach
- Start with
k = 0. - While
wordrepeatedk + 1times is a substring ofsequence, incrementk. - Return
k.
Why it works
Monotonicity holds because any occurrence of word^(k+1) contains an occurrence of word^k as a prefix. The loop cannot run more than sequence.length / word.length times, since the repeated string outgrows the sequence.
Complexity
- Time —
O(n²/m) in the worst case, well within the stated limits - Space —
O(n) for the repeated string
Pitfalls
- Counting non-overlapping occurrences of
wordanywhere is wrong — the copies must be consecutive. - Starting
kat 1 and returning it unconditionally reports 1 whenwordnever occurs. - Binary searching
kworks but is unnecessary and easy to get off by one.
Reference solution
Python
def maxRepeating(sequence: str, word: str) -> int:
k = 0
while word * (k + 1) in sequence:
k += 1
return kJava
public static int maxRepeating(String sequence, String word) {
int k = 0;
StringBuilder cur = new StringBuilder(word);
while (sequence.contains(cur.toString())) {
k++;
cur.append(word);
}
return k;
}C++
int maxRepeating(string sequence, string word) {
int k = 0;
string cur = word;
while (sequence.find(cur) != string::npos) {
k++;
cur += word;
}
return k;
}JavaScript
var maxRepeating = function(sequence, word) {
let k = 0;
let cur = word;
while (sequence.indexOf(cur) !== -1) {
k++;
cur += word;
}
return k;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings