Longest Duplicate Substring

Hard

Given a string s, consider all duplicated substrings: (contiguous) substrings that occur two or more times (the occurrences may overlap). Return the longest such substring; if there are several of the maximum length, return the lexicographically smallest one. If none exists, return "".

Example 1

Input:  s = "banana"
Output: "ana"

Example 2

Input:  s = "abcd"
Output: ""

Example 3

Input:  s = "aaaa"
Output: "aaa"

Constraints

• 1 <= s.length <= 16
• s consists of lowercase English letters.