Maximum Repeating Substring solution and explanation
Google
9 more videos on this problem
1668. Maximum Repeating Substring (Leetcode Easy)Programming Live with Larry · 3:25 · 3K views
Maximum Repeating Substring | LeetCode 1668 | LeetCode BiWeekly 40 | Java | HindiPepcoding · 4:08 · 2K views
1668. Maximum Repeating Substring || Java || Leetcode || HindiCoding Sphere · 9:17 · 2K views
LEETCODE #1668 Maximum Repeating Substring Python Solution ExplainedMr. Logic · 5:19 · 1K views
Leetcode Problem 1668 - Maximum Repeating Substring | Java | Crack FAANG | Crack Coding interviewSoftWiz Circle · 3:42 · 615 views
Leetcode solving: 1668. Maximum Repeating SubstringMath Geeks · 2:35 · 282 views
LeetCode 1668 | Maximum Repeating Substring | JavaSleepy Cracker · 3:44 · 175 views
LeetCode - 1668. Maximum Repeating Substring | String | JavaOrkhan Gasanov · 2:11 · 84 views
Leetcode 1668. Maximum Repeating Substring (kmp)LetsCode · 15:23 · 67 views
Day 405: LeetCode Problem 1668. Maximum Repeating Substring - SwiftiOSxBank · 5:47 · 65 views
The problem
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.
def maxRepeating(sequence: str, word: str) -> int:
max_k = 0
repeated = ''
while True:
repeated += word
if repeated not in sequence:
break
max_k += 1
return max_kclass Solution {
public int maxRepeating(String sequence, String word) {
int maxK = 0;
StringBuilder repeated = new StringBuilder();
while (true) {
repeated.append(word);
if (!sequence.contains(repeated))
break;
maxK++;
}
return maxK;
}
}#include <string>
int maxRepeating(std::string sequence, std::string word) {
int maxK = 0;
std::string repeated;
while (true) {
repeated += word;
if (sequence.find(repeated) == std::string::npos)
break;
maxK++;
}
return maxK;
}function maxRepeating(sequence, word) {
let maxK = 0;
let repeated = '';
while (true) {
repeated += word;
if (!sequence.includes(repeated))
break;
maxK++;
}
return maxK;
}#include <string.h>
int maxRepeating(char *sequence, char *word) {
int maxK = 0;
char repeated[1000] = "";
while (1) {
strcat(repeated, word);
if (strstr(sequence, repeated) == NULL)
break;
maxK++;
}
return maxK;
}public class Solution {
public int MaxRepeating(string sequence, string word) {
int maxK = 0;
string repeated = string.Empty;
while (true) {
repeated += word;
if (!sequence.Contains(repeated))
break;
maxK++;
}
return maxK;
}
}The Python implementation uses the in-built substring checking with the in keyword to check for the presence of the repeating word.
Time Complexity: O((n + m) * l)
Space Complexity: O(k * m)
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.
def maxRepeating(sequence: str, word: str) -> int:
def is_repeating(k):
return word * k in sequence
left, right = 0, len(sequence) // len(word)
result = 0
while left <= right:
mid = (left + right) // 2
if is_repeating(mid):
result = mid
left = mid + 1
else:
right = mid - 1
return resultclass Solution {
public int maxRepeating(String sequence, String word) {
int left = 0, right = sequence.length() / word.length();
int result = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
StringBuilder repeated = new StringBuilder();
for (int i = 0; i < mid; ++i)
repeated.append(word);
if (sequence.contains(repeated)) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
}#include <string>
int maxRepeating(std::string sequence, std::string word) {
int left = 0, right = sequence.size() / word.size();
int result = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
std::string repeated;
for (int i = 0; i < mid; ++i)
repeated += word;
if (sequence.find(repeated) != std::string::npos) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}function maxRepeating(sequence, word) {
let left = 0, right = Math.floor(sequence.length / word.length);
let result = 0;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
const repeated = word.repeat(mid);
if (sequence.includes(repeated)) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}#include <string.h>
int maxRepeating(char *sequence, char *word) {
int left = 0, right = strlen(sequence) / strlen(word);
int result = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
char repeated[1000] = "";
for (int i = 0; i < mid; i++)
strcat(repeated, word);
if (strstr(sequence, repeated) != NULL) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}public class Solution {
public int MaxRepeating(string sequence, string word) {
int left = 0, right = sequence.Length / word.Length;
int result = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
var repeated = new StringBuilder();
for (int i = 0; i < mid; ++i)
repeated.Append(word);
if (sequence.Contains(repeated.ToString())) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
}The is_repeating function is a helper to check if the concatenation is a substring. It forms part of a binary search that controls the bounds of the concatenation length test.
Time Complexity: O((n + m) * log(n/m))
Space Complexity: O(k * m)
Approach 3: Default Approach
function maxRepeating(sequence: string, word: string): number {
let n = sequence.length;
let m = word.length;
for (let k = Math.floor(n / m); k > 0; k--) {
if (sequence.includes(word.repeat(k))) {
return k;
}
}
return 0;
}func maxRepeating(sequence string, word string) int {
for k := len(sequence) / len(word); k > 0; k-- {
if strings.Contains(sequence, strings.Repeat(word, k)) {
return k
}
}
return 0
}impl Solution {
pub fn max_repeating(sequence: String, word: String) -> i32 {
let n = sequence.len();
let m = word.len();
if n < m {
return 0;
}
let mut dp = vec![0; n - m + 1];
for i in 0..=n - m {
let s = &sequence[i..i + m];
if s == word {
dp[i] = (if (i as i32) - (m as i32) < 0 {
0
} else {
dp[i - m]
}) + 1;
}
}
*dp.iter().max().unwrap()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O((n + m) * l) Space Complexity: O(k * m) |
| Optimized Approach Using Binary Search | Time Complexity: O((n + m) * log(n/m)) Space Complexity: O(k * m) |
| Default Approach | – |
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. |
Frequently asked questions
Is Maximum Repeating Substring easy or hard?
Maximum Repeating Substring is classified as an Easy problem on LeetCode. The logic is straightforward once you recognize that the task is simply counting how many times a pattern can repeat while still appearing inside another string.
How to solve Maximum Repeating Substring in O(n)?
Strict O(n) solutions typically require specialized string matching techniques such as KMP-style pattern tracking or preprocessing repeated patterns. In most interview implementations, binary search combined with substring checks is considered efficient enough and simpler to implement.
Maximum Repeating Substring Python or Java solution?
Both Python and Java solutions typically construct repeated strings using multiplication or concatenation and check substring presence using built-in methods like 'in' in Python or 'contains' in Java. The same logic works across C++, JavaScript, and C# with similar string operations.
What is the best approach for Maximum Repeating Substring?
Binary search on the repetition count is the most efficient practical approach. Instead of checking every possible repetition, it searches the valid range of k and verifies whether word repeated k times appears in sequence. This reduces the number of substring checks and runs in about O(n log k) time.
Is Maximum Repeating Substring asked at Google/Amazon/Meta?
This problem reflects common string manipulation and pattern repetition questions frequently asked in interviews at large tech companies. Variants involving repeated patterns, substring search, and string matching appear in interview rounds at companies like Amazon, Google, and Meta.
What data structure is used in Maximum Repeating Substring?
The problem mainly uses basic string operations and substring matching. Some optimized reasoning uses binary search over integers representing repetition counts. No complex data structures are required beyond standard string handling.
What is the time complexity of Maximum Repeating Substring?
The brute force method checks each repetition sequentially and performs substring searches, leading to roughly O(n * m * k) time in the worst case. The optimized binary search approach reduces the checks to logarithmic steps, giving around O(n log k) time with constant extra space.