DSA problem
Longest Duplicate Substring
Given a string s, consider all duplicated substrings — contiguous substrings of s that occur two or more times. The occurrences may overlap. Return any duplicated substring that has the longest possible length. If s does not have a duplicated substring, return an empty string.
A brute force enumeration of every pair of substrings is O(n^4) and useless beyond toy inputs. The decisive observation is monotonicity: if a duplicate of length L exists, then a duplicate of every length less than L also exists (just take a substring of a duplicate). This monotonic structure invites a binary search on the answer length.
For each candidate length L, we need a fast way to check whether some substring of length L appears at least twice. The natural choice is a rolling hash (Rabin-Karp): slide a window of size L across s, compute a polynomial hash of each window in O(1) per step, and store seen hashes in a set. If the same hash repeats, we have a candidate duplicate. To guard against hash collisions, verify candidates by comparing the actual substrings — keeping the start indices in the hash map makes this trivial.
Binary search runs O(log n) iterations. Each iteration costs O(n) for the rolling hash scan and O(L) per verification (rare on good hash functions). Using a large prime modulus and a random base modulo a large prime keeps the expected collision rate negligible. The overall expected time is O(n log n) and space O(n) for the hash table. Tracking the longest substring seen across all successful iterations yields the answer.
Examples
s = "banana""ana"s = "abcd"""s = "aaaaa""aaaa"Constraints
- 2 <= s.length <= 3 * 10^4
- s consists of lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.