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.
Given a string `s`, find the longest substring that occurs in `s` at least twice and return it. Occurrences may overlap. Return the empty string when no substring occurs twice.
Implement `longest_repeated_substring(s)`, which returns that substring.
### 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.
### 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"`, so it is returned even though `"cd"` appears first.
### Constraints
- `1 <= len(s) <= 3 * 10^4`
- `s` consists only of lowercase English letters `a` to `z`.
The return value is always a substring of `s` or the empty string; no integer crosses the function boundary, so no value can exceed 2^31 - 1.
Constraints
- 1 <= len(s) <= 3 * 10^4
- s consists only of lowercase English letters 'a' to 'z'.
Examples
Input: ('a',)
Expected Output: ''
Explanation: Minimum length 1: a single character cannot occur twice, so the answer is empty.
Input: ('aa',)
Expected Output: 'a'
Explanation: Smallest input with a repeat: 'a' occurs at positions 0 and 1, while 'aa' occurs once.
Hints
- Occurrences may overlap: in a string made of one repeated letter, the longest repeated substring is only one character shorter than the whole string.
- If a substring of length L occurs at two different positions, then every shorter piece cut from the same two starting positions also occurs twice, so the achievable repeat lengths have no gaps.
- With up to 3 * 10^4 characters, comparing every pair of starting positions character by character is far too slow; aim for close to n log n work, and apply the smallest-string tie-break only among candidates of the maximum length.