Write longest_dup_substring(s) -> str returning a longest substring that appears at least twice in s (the two occurrences may overlap). If several different substrings share the maximum length, return any of them. If no substring repeats, return "".
longest_dup_substring("mississippi") # "issi" (at positions 1 and 4, overlapping)
longest_dup_substring("abcd") # ""
longest_dup_substring("zzzz") # "zzz"
Constraints: 2 <= len(s) <= 3 * 10**4, lowercase letters.
Aim for about O(n log n). Trying lengths one by one, or comparing all pairs of positions, is far too slow when the answer is long.
Show hint
If some length-L substring repeats, so does some length-L - 1 substring, so the answer length can be searched for rather than scanned. To test one length in O(n), give each window a fingerprint you can slide in O(1) and look for two equal ones (confirming real matches).