Longest Duplicate Substring
Hard · Arrays & Hashing · String · Binary Search · Sliding Window · Rolling Hash · Hash Function
Problem
You are given a string s. A duplicated substring is a contiguous piece of s that occurs in it at least twice; the two occurrences may overlap.
Return any duplicated substring of the greatest possible length. If no substring occurs twice, return the empty string "".
Examples
Input: s = "mississippi" Output: "issi"
"issi" occurs at positions 1 and 4; the two occurrences share the middle "i". Nothing longer repeats.
Input: s = "abcd" Output: ""
Every letter is different, so no substring occurs twice.
Input: s = "aaaa" Output: "aaa"
"aaa" occurs at positions 0 and 1.
Constraints
- 2 <= len(s) <= 3 · 10^4
- s consists of lowercase English letters
Approaches
- Grow the length, storing every window — time O(n · L²) for an answer of length L, O(n³) worst case, space O(n · L)
Follow-up
A suffix array with its LCP array solves this in O(n log n) (or O(n) with a linear-time construction) without hashing: the longest duplicate is the largest LCP value between neighboring suffixes. A suffix automaton gives O(n) as well.
Related problems
Start free on Cariara · Coding problems · System design studio
