Funcia
Lv.3binary-searchhashingrolling-hashstring

Longest Repeated Substring

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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

sresult
"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

  • 1≤N=1 \le N = s.length ≤200,000\le 200{,}000
  • s consists of lowercase English letters only.

Expected complexity

Time
O(N log N)
Space
O(N)

Examples

sExpected
"banana"3
"abcd"0
"aaaaa"4

Hint

Hint

If some length-LL substring repeats, so does a shorter one, so binary search on LL. To test a length, hash every length-LL window with a rolling hash (O(1)O(1) each from prefix hashes) and look for a duplicate in a set or a sorted list; use a large modulus such as 261−12^{61} - 1 or two moduli to avoid collisions. (A suffix array with LCP also works.) Comparing all pairs of positions is O(N2)O(N^2) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)406 msestimated
C++ (GCC, gnu++23)406 msderived
Python 3.131762 msderived
Java 251538 msderived
Kotlin 2.4 (JVM)1812 msestimated
C# 14 (.NET 10)1812 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.