Longest Repeated Substring
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
Given a string s, return the length of the longest substring (contiguous) that occurs starting at two different
positions of s. The two occurrences may overlap. Return 0 if no substring occurs twice.
Examples
| s | result |
|---|---|
"banana" | 3 |
"abcd" | 0 |
"aaaaa" | 4 |
Example 1 — "ana" occurs at positions 1 and 3 (the occurrences overlap).
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(s: string) → int
Constraints
-
s.length sconsists of lowercase English letters only.
Expected complexity
- Time
- O(N log N)
- Space
- O(N)
Examples
| s | Expected |
|---|---|
"banana" | 3 |
"abcd" | 0 |
"aaaaa" | 4 |
Hint
Hint
If some length- substring repeats, so does a shorter one, so binary search on . To test a length, hash every length- window with a rolling hash ( each from prefix hashes) and look for a duplicate in a set or a sorted list; use a large modulus such as or two moduli to avoid collisions. (A suffix array with LCP also works.) Comparing all pairs of positions is and exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 406 ms | estimated |
| C++ (GCC, gnu++23) | 406 ms | derived |
| Python 3.13 | 1762 ms | derived |
| Java 25 | 1538 ms | derived |
| Kotlin 2.4 (JVM) | 1812 ms | estimated |
| C# 14 (.NET 10) | 1812 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 11 | verdict only |
| performance | 60 | 4 | verdict only |