#1044
Longest Duplicate Substring
Hard Binary search + Rabin-Karp
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return any longest substring that appears at least twice in s (occurrences may overlap), or "" if none.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the longest piece that appears at least twice.
Why this works: if a length-L duplicate exists, shorter ones do too, so binary search L. For each L, rolling hashes find repeated windows quickly.
Example: "banana"
L=3: "ana" appears at 1 and 3 ✓L=4: "bana","anan","nana" all different ✗answer "ana"
✦Hints open one at a time
If a duplicate of length L exists, a duplicate of every shorter length exists too — binary search on L.
To test a length L, hash every substring of length L with a rolling hash and look for a repeat.
Confirm a hash hit by comparing the actual substrings, to rule out collisions.
↗Approach
Binary search L. For each L, compute Rabin-Karp hashes with a large modulus, store hash → list of start indexes, and on a hit compare characters with regionMatches. Keep the start of the longest found.
</>Solution (Java)
import java.util.*;
class Solution {
private static final long MOD = 1_000_000_007L, BASE = 131;
public String longestDupSubstring(String s) {
int lo = 1, hi = s.length() - 1, bestStart = -1, bestLen = 0;
while (lo <= hi) {
int mid = (lo + hi) >>> 1;
int start = find(s, mid);
if (start >= 0) {
bestStart = start;
bestLen = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return bestStart < 0 ? "" : s.substring(bestStart, bestStart + bestLen);
}
// returns a start index of a substring of length len that repeats, or -1
private int find(String s, int len) {
long hash = 0, power = 1;
for (int i = 0; i < len; i++) {
hash = (hash * BASE + s.charAt(i)) % MOD;
power = power * BASE % MOD;
}
Map<Long, List<Integer>> seen = new HashMap<>();
seen.computeIfAbsent(hash, k -> new ArrayList<>()).add(0);
for (int i = len; i < s.length(); i++) {
hash = (hash * BASE + s.charAt(i)) % MOD;
hash = (hash - s.charAt(i - len) * power % MOD + MOD) % MOD; // drop the old char
int start = i - len + 1;
List<Integer> list = seen.computeIfAbsent(hash, k -> new ArrayList<>());
for (int other : list) {
if (s.regionMatches(other, s, start, len)) return start; // real match
}
list.add(start);
}
return -1;
}
}!Common mistake
Trusting hashes without verifying — collisions give wrong answers on big tests.
Complexity
- Time: O(n log n) on average.
- Space: O(n).
Topic: String Pattern Matching
🎬 Episodes 18–19: video coming soon