Longest Substring That Occurs at Least Twice, Overlaps Allowed
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a string `s`, find the longest substring that occurs in `s` at least twice. The occurrences may overlap. Return that substring, or the empty string when no substring occurs twice.
### Function Signature
```python
def longest_repeated_substring(s: str) -> str:
```
### Rules
- A substring is a contiguous, non-empty block of characters of `s`.
- A substring is repeated when it occurs at two or more different starting positions in `s`. Occurrences may overlap: in `"aaaa"`, the substring `"aaa"` occurs at positions `0` and `1`.
- Return the longest repeated substring. If several different repeated substrings share the maximum length, return the lexicographically smallest of them (ordinary character-by-character string order).
- Return `""` when no substring is repeated, that is, when all characters of `s` are different.
### Constraints
- `1 <= len(s) <= 3 * 10^4`
- `s` consists only of lowercase English letters `a` to `z`.
### Examples
**Example 1**
```text
Input: s = "banana"
Output: "ana"
```
`"ana"` occurs at positions `1` and `3`; the two occurrences share the middle `"a"`. No substring of length 4 occurs twice.
**Example 2**
```text
Input: s = "cdcdabab"
Output: "ab"
```
`"cd"` and `"ab"` each occur twice, and no substring of length 3 occurs twice. `"ab"` is lexicographically smaller than `"cd"`.
**Example 3**
```text
Input: s = "abcd"
Output: ""
```
Every character occurs once, so no substring is repeated.
Overview: A string algorithms problem: given a lowercase string of up to 30,000 characters, return the longest substring that occurs at least twice, where occurrences may overlap and ties go to the lexicographically smallest substring. It tests efficient repeated-substring search on long inputs, where a quadratic scan is too slow.