Link: https://leetcode.com/problems/longest-repeating-substring/
Solution:
Topics: rabin-karp, binary search, Longest duplicate substring
Intuition
This is essentially the same problem as Longest duplicate substring, but the constraints are not as extreme and we only need to return the length of the string, not the repeating string itself.
There is also a DP solution but it’s Bottom-up DP (which I despise) with no obvious top down implementation.
The key idea here is that if the longest substring s
is repeating, then s[:-1]
is also repeating, and s[:-2]
is also repeating and so on. This sorted order should immediately bring our attention to binary search.
Basically, we search for a substring length in the range 1-(len(s)-1)
, and use the rabin-karp rolling hash to compare slices in o(1)
time.
Python has a very nice native rabin-karp implementation:
Implementation
Review 1
Came up with this solution easily, but it would be ideal to have rabin-karp in my back pocket for this types of problems…not sure if memoryview
would particularly impress anyone.