Longest duplicated substring in a string

Given a string of lowercase letters, return any one of the longest substrings that occurs at least twice. The two occurrences may overlap. If no substring repeats, return the empty string. Do substantially better than comparing every pair of substrings.

Interface

Unless you agree on a different interface with the interviewer, assume:

• longest_dup_substring(s: str) -> str — any longest substring that appears at two or more starting positions, or "".

Example

longest_dup_substring("banana")    ->  "ana"     # at 1 and 3; the occurrences overlap
longest_dup_substring("abcd")      ->  ""
longest_dup_substring("aaaa")      ->  "aaa"     # at 0 and 1
longest_dup_substring("abcabcab")  ->  "abcab"   # at 0 and 3

Constraints

• 1 <= len(s) <= 2 · 10^5, lowercase English letters only.

Clarifying questions

• May the two occurrences overlap?
• If several substrings tie for longest, may I return any of them?
• Is the alphabet only lowercase letters?
• Is a probabilistic method (hashing) acceptable, or must it be exact?

What a strong answer covers

• The monotone property: if a length L repeats, every shorter length does too. So binary search on L.
• For a given L, slide a Rabin-Karp rolling hash over all windows and look for a repeat. O(n) per check, O(n log n) total.
• Collisions: verify a hash match by comparing the substrings, or use two moduli, and explain the cost of each.
• The exact alternatives: a suffix array with the LCP array (the answer is the maximum LCP of adjacent suffixes), or a suffix automaton. O(n log n) or O(n).
• Tests: no repeat, all one letter, the answer at the very end, overlapping occurrences.

Follow-ups

• Return the longest substring that appears at least k times.
• Occurrences must not overlap.
• Find the longest substring common to two different strings.