Longest Duplicate Substring
Understanding the Problem
We need to find the longest substring that appears at least twice in the given string. The two occurrences are allowed to overlap. In "banana", the substring "ana" starts at index 1 and again at index 3, and those two occurrences share the character 'a' at index 3.
A naive way to think about this: generate every possible substring, check if it appears more than once, and track the longest one. The number of substrings is O(n^2), and comparing them takes O(n) each, so that would be O(n^3). For n up to 30,000, that is far too slow.
Substring length has a monotonic property. If a duplicate substring of length k exists, then a duplicate substring of length k-1 also exists (trim the last character from each occurrence). The set of lengths that have a duplicate forms a contiguous range starting from 0, so we can binary search on the length of the answer. For each candidate length, we only check whether any duplicate substring of that exact length exists. A rolling hash (Rabin-Karp) makes that check fast by comparing substrings in O(1) amortized time.
Key Constraints:
2 <= s.length <= 3 * 10^4→ With n up to 30,000, an O(n^2 log n) brute force that builds substrings reaches the hundreds of billions of operations, so the solution needs to be closer to O(n log n).sconsists of lowercase English letters → Only 26 distinct characters, which lets the rolling hash map each character to an integer 0-25 and use base 26.
Approach 1: Brute Force
Intuition
Try every possible substring length from longest to shortest. For each length L, collect all substrings of that length in a hash set as we scan left to right. If a substring is already in the set, it appeared earlier at the same length, so it is a duplicate. Since we test lengths from longest to shortest, the first duplicate found is one of the longest possible, so we return it immediately.
Algorithm
- For each possible length L from n-1 down to 1:
- Extract every substring of length L.
- Store each substring in a set.
- If we find a substring already in the set, return it.
- If no duplicate found at any length, return "".
Example Walkthrough
Code
- Time Complexity: O(n^3). We try O(n) different lengths. For each length L, we extract O(n) substrings, and each substring extraction and hashing takes O(L) time.
- Space Complexity: O(n^2). The hash set stores up to O(n) substrings of length up to O(n).
This wastes work in two ways. It checks every length from n-1 down to 1 even though the monotonicity property lets us binary search instead, and it rebuilds each length's substrings from scratch instead of updating a rolling hash in O(1). The next approach fixes both.
Approach 2: Binary Search + Rabin-Karp Rolling Hash
Intuition
Two ideas combine into an efficient solution.
The first is monotonicity. The question "does a duplicate of length L exist?" answers YES for every length below some threshold and NO for every length above it, because trimming a character off a duplicate of length k leaves a duplicate of length k-1. With that single YES-to-NO boundary, binary search finds the largest valid length in O(log n) steps instead of scanning every length.
The second is the rolling hash (Rabin-Karp). To check whether a duplicate of length L exists, slide a window of size L across the string and hash each window. Two equal substrings always produce equal hashes, so a duplicate substring shows up as a repeated hash. A polynomial hash updates in O(1) when the window moves one position right: multiply by the base, subtract the contribution of the character leaving on the left, and add the character entering on the right. That makes one length's check O(n) rather than O(n * L).
Binary search runs O(log n) checks and each check is O(n), giving O(n log n) overall.
Equal hashes do not guarantee equal substrings: two different substrings can collide on the same hash value. So when two windows share a hash, the algorithm compares their characters directly before reporting a duplicate. This keeps the answer exact regardless of hash collisions. The large prime modulus only keeps collisions rare enough that the verification cost stays low; it is not relied on for correctness.
Algorithm
- Binary search on the length L, with low = 1 and high = n - 1.
- For each candidate length mid = (low + high) / 2, check if a duplicate substring of length mid exists.
- The check uses Rabin-Karp: compute the rolling hash of each substring of length mid. Store hashes in a map. If a hash collision occurs, verify by comparing actual characters.
- If a duplicate of length mid exists, record the result and search for longer (low = mid + 1).
- If no duplicate of length mid exists, search for shorter (high = mid - 1).
- Return the longest duplicate found, or "" if none exists.
Example Walkthrough
Code
- Time Complexity: O(n log n) average case. Binary search runs O(log n) iterations. Each Rabin-Karp check processes O(n) substrings with O(1) hash updates. The worst case is O(n^2 log n) if many substrings collide on the same hash and force character-by-character verification, which a large prime modulus makes rare.
- Space Complexity: O(n). The hash map stores at most O(n) entries per binary search iteration.
The O(n log n) figure is an average case that depends on hash collisions staying rare. The next approach avoids hashing entirely and gives a deterministic bound using a suffix array.
Approach 3: Suffix Array + LCP Array
Intuition
A suffix array lists the starting indices of all suffixes of the string in lexicographic order. The Longest Common Prefix (LCP) array stores, for each adjacent pair of suffixes in that sorted order, the length of the prefix they share. The maximum value in the LCP array is the length of the longest duplicate substring, and the suffix it belongs to gives the starting position.
For "banana", the sorted suffixes are "a", "ana", "anana", "banana", "na", "nana". The LCP between "ana" and "anana" is 3, the substring "ana", which is the answer.
Building the suffix array takes O(n log n) to O(n log^2 n) depending on the construction, and computing the LCP array from it takes O(n) with Kasai's algorithm.
Every substring of s is a prefix of some suffix of s, so a substring that occurs twice is a common prefix of two distinct suffixes. Sorting the suffixes places any two suffixes that share a long prefix next to each other, which means the longest such shared prefix is the largest gap between two lexicographically adjacent suffixes. That value is exactly the maximum LCP. Kasai's algorithm computes the LCP values in original-string order rather than sorted order, using the fact that if suffix i shares h characters with its sorted predecessor, then suffix i+1 shares at least h-1. That lower bound lets it skip re-comparing those h-1 characters, which is what keeps the LCP pass at O(n).
Algorithm
- Build the suffix array: sort all suffixes of s lexicographically. Store their starting indices in sorted order.
- Compute the LCP array using Kasai's algorithm: for each pair of adjacent suffixes in sorted order, compute the length of their common prefix.
- Find the maximum value in the LCP array. The corresponding suffix gives us the starting position of the longest duplicate substring.
- Extract and return the substring.
Example Walkthrough
Code
- Time Complexity: O(n log^2 n). Suffix array construction using doubling + comparison sort takes O(n log^2 n). Each of the O(log n) doubling rounds does an O(n log n) sort. Kasai's LCP computation takes O(n).
- Space Complexity: O(n). The suffix array, rank array, and LCP array each take O(n) space.