Return any longest substring of s that occurs at least twice; occurrences may overlap. If no substring repeats, return the empty string. s can have up to 30,000 characters.
Before you code
Every repeated substring is a common prefix of two suffixes. Which two suffixes, after sorting, share the longest prefix?
Hints
- Suffix array approach: build the suffix array by prefix doubling, then the LCP array with Kasai's algorithm. The largest LCP value and its position give the answer.
- Hashing approach: if a substring of length L repeats, so does one of every shorter length. Binary search on L, and for each L, roll a hash over all windows and look for a repeat.
- With hashing, verify a candidate repeat by comparing the substrings, or use two moduli, since a collision would return a wrong answer.
Production & complexity notes
When solving Longest duplicate substring on LeetCode (hard), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Suffix arrays in practice to reinforce the underlying pattern.
What it practices
The LCP array, from Suffix arrays in practice, and binary search over rolling hashes, from Rolling hash and Rabin-Karp.