#1044
Longest Duplicate Substring
hard · verified · 31.1% accepted · 2,338 likes · top 9%
string · binary search · sliding window · rolling hash · suffix array · hash function
Description
Given a string s, consider all duplicated substrings: (contiguous) substrings of s that occur 2 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, the answer is "".
Example 1:
Input: s = "banana"
Output: "ana"
Example 2:
Input: s = "abcd"
Output: ""
Solution