906. Longest Repeated Piece
An archivist compares the letters of a manuscript s and wants the longest passage that is copied somewhere else in the same manuscript. Two occurrences of a passage are different when they start at different indices; they are allowed to overlap.
Return the longest substring of s that occurs at least twice. If several different substrings share the maximum length, return the lexicographically smallest of them. If no substring occurs twice, return the empty string.
Aim for time O(n log n) where n is the length of s. Checking every length and every pair of start positions is far too slow.
Example 1
- Input:
- s = "xyzzyxyzzyz"
- Output:
- "xyzzy"
- Explanation:
The piece 'xyzzy' occurs at index 0 and index 5 and is the longest repeat.
Example 2
- Input:
- s = "tutututu"
- Output:
- "tututu"
- Explanation:
'tututu' appears at index 0 and index 2, which overlap; this is the longest repeated piece.
Example 3
- Input:
- s = "quartzmen"
- Output:
- ""
- Explanation:
No letter occurs twice, so no substring occurs twice, so the answer is the empty string.
Constraints
1 ≤ s.length ≤ 40000
s contains only lowercase English letters.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)