Longest Repeating Substring
MediumUpdated: Aug 2, 2025
Practice on:
Problem
Given a string s, return the length of the longest repeating substrings.
If no repeating substring exists, return 0.
Examples
Example 1:
Input: s = "abcd"
Output: 0
Explanation: There is no repeating substring.
Example 2:
Input: s = "abbaba"
Output: 2
Explanation: The longest repeating substrings are "ab" and "ba", each of which occurs twice.
Example 3:
Input: s = "aabcaabdaab"
Output: 3
Explanation: The longest repeating substring is "aab", which occurs 3 times.
Constraints:
1 <= s.length <= 2000sconsists of lowercase English letters.
Solution
Method 1 – Binary Search with Rolling Hash
Intuition
To find the longest repeating substring, we can use binary search on the substring length and check for duplicates using a rolling hash (Rabin-Karp). This efficiently narrows down the maximum length by checking if any substring of a given length repeats.
Approach
- Set left and right pointers for binary search on substring length (from 1 to n-1).
- For each length mid, use a rolling hash to check if any substring of that length repeats:
- Compute hash for the first substring of length mid.
- Slide the window, updating the hash in O(1) time, and check for duplicates using a set.
- If a duplicate is found, move left up; otherwise, move right down.
- Return the maximum length found.
Code
C++
class Solution {
public:
int longestRepeatingSubstring(string s) {
int n = s.size(), l = 1, r = n, ans = 0;
while (l <= r) {
int m = (l + r) / 2;
unordered_set<long long> seen;
long long h = 0, a = 26, mod = 1e9+7, pow = 1;
for (int i = 0; i < m; ++i) h = (h * a + s[i] - 'a') % mod, pow = (pow * a) % mod;
seen.insert(h);
bool found = false;
for (int i = m; i < n; ++i) {
h = (h * a - (s[i-m] - 'a') * pow % mod + mod) % mod;
h = (h + s[i] - 'a') % mod;
if (seen.count(h)) { found = true; break; }
seen.insert(h);
}
if (found) ans = m, l = m + 1;
else r = m - 1;
}
return ans;
}
};
Go
func longestRepeatingSubstring(s string) int {
n := len(s)
l, r, ans := 1, n, 0
for l <= r {
m := (l + r) / 2
seen := map[int64]struct{}{}
var h, a, mod, pow int64 = 0, 26, 1e9+7, 1
for i := 0; i < m; i++ {
h = (h*a + int64(s[i]-'a')) % mod
pow = (pow * a) % mod
}
seen[h] = struct{}{}
found := false
for i := m; i < n; i++ {
h = (h*a - int64(s[i-m]-'a')*pow%mod + mod) % mod
h = (h + int64(s[i]-'a')) % mod
if _, ok := seen[h]; ok {
found = true
break
}
seen[h] = struct{}{}
}
if found {
ans = m
l = m + 1
} else {
r = m - 1
}
}
return ans
}
Java
class Solution {
public int longestRepeatingSubstring(String s) {
int n = s.length(), l = 1, r = n, ans = 0;
while (l <= r) {
int m = (l + r) / 2;
Set<Long> seen = new HashSet<>();
long h = 0, a = 26, mod = 1000000007, pow = 1;
for (int i = 0; i < m; ++i) {
h = (h * a + s.charAt(i) - 'a') % mod;
pow = (pow * a) % mod;
}
seen.add(h);
boolean found = false;
for (int i = m; i < n; ++i) {
h = (h * a - (s.charAt(i-m) - 'a') * pow % mod + mod) % mod;
h = (h + s.charAt(i) - 'a') % mod;
if (seen.contains(h)) { found = true; break; }
seen.add(h);
}
if (found) { ans = m; l = m + 1; }
else r = m - 1;
}
return ans;
}
}
Kotlin
class Solution {
fun longestRepeatingSubstring(s: String): Int {
val n = s.length
var l = 1
var r = n
var ans = 0
while (l <= r) {
val m = (l + r) / 2
val seen = mutableSetOf<Long>()
var h = 0L
val a = 26L
val mod = 1_000_000_007L
var pow = 1L
for (i in 0 until m) {
h = (h * a + (s[i] - 'a')) % mod
pow = (pow * a) % mod
}
seen.add(h)
var found = false
for (i in m until n) {
h = (h * a - (s[i-m] - 'a') * pow % mod + mod) % mod
h = (h + (s[i] - 'a')) % mod
if (h in seen) { found = true; break }
seen.add(h)
}
if (found) {
ans = m
l = m + 1
} else {
r = m - 1
}
}
return ans
}
}
Python
class Solution:
def longestRepeatingSubstring(self, s: str) -> int:
n = len(s)
l, r, ans = 1, n, 0
a, mod = 26, 10**9+7
while l <= r:
m = (l + r) // 2
h, pow_a = 0, 1
seen = set()
for i in range(m):
h = (h * a + ord(s[i]) - ord('a')) % mod
pow_a = (pow_a * a) % mod
seen.add(h)
found = False
for i in range(m, n):
h = (h * a - (ord(s[i-m]) - ord('a')) * pow_a % mod + mod) % mod
h = (h + ord(s[i]) - ord('a')) % mod
if h in seen:
found = True
break
seen.add(h)
if found:
ans = m
l = m + 1
else:
r = m - 1
return ans
Rust
impl Solution {
pub fn longest_repeating_substring(s: String) -> i32 {
let n = s.len();
let s = s.as_bytes();
let (mut l, mut r, mut ans) = (1, n, 0);
while l <= r {
let m = (l + r) / 2;
let mut seen = std::collections::HashSet::new();
let (mut h, a, mod_, mut pow) = (0u64, 26u64, 1_000_000_007u64, 1u64);
for i in 0..m {
h = (h * a + (s[i] - b'a') as u64) % mod_;
pow = (pow * a) % mod_;
}
seen.insert(h);
let mut found = false;
for i in m..n {
h = (h * a + (s[i] - b'a') as u64) % mod_;
h = (h + mod_ - ((s[i-m] - b'a') as u64 * pow % mod_)) % mod_;
if seen.contains(&h) {
found = true;
break;
}
seen.insert(h);
}
if found {
ans = m;
l = m + 1;
} else {
r = m - 1;
}
}
ans as i32
}
}
TypeScript
class Solution {
longestRepeatingSubstring(s: string): number {
const n = s.length;
let l = 1, r = n, ans = 0;
const a = 26, mod = 1e9+7;
while (l <= r) {
const m = Math.floor((l + r) / 2);
let h = 0, pow = 1;
const seen = new Set<number>();
for (let i = 0; i < m; ++i) {
h = (h * a + s.charCodeAt(i) - 97) % mod;
pow = (pow * a) % mod;
}
seen.add(h);
let found = false;
for (let i = m; i < n; ++i) {
h = (h * a - (s.charCodeAt(i-m) - 97) * pow % mod + mod) % mod;
h = (h + s.charCodeAt(i) - 97) % mod;
if (seen.has(h)) { found = true; break; }
seen.add(h);
}
if (found) { ans = m; l = m + 1; }
else r = m - 1;
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n log n), as we binary search over substring length and check all substrings of a given length. - 🧺 Space complexity:
O(n), for the hash set storing substring hashes.