Link: https://leetcode.com/problems/longest-duplicate-substring/
Solution:
Topics: binary search, rabin-karp
Intuition
Very tricky problem. Binary search is used because if there exists a duplicate substring of length n, then there is guaranteed to be a duplicate substring of length n-1. The idea is to perform binary search with a sliding window to check if there exists a duplicate substring.
The optimal solution requires the rabin-karp algorithm because a simple sliding window and set requires slicing the string, and slicing is o(length) time complexity. Rabin-karp allows us to slice and hash a substring in O(1) time.
Rabin-karp is pretty complicated to code by hand, but python provides a very nice class memoryview that allows for O(1) slicing! The reason being is that when you slice the memoryview object, it does not create a new object, only a reference to the underlying data.
Implementation
def longest_dup(s):
def has_dup(length):
has = set()
l = 0
for r in range(length, len(s)+1):
curr = s_data[l:r]
if curr in has:
return s[l:r]
has.add(curr)
l += 1
return ''
s_data = memoryview(s.encode()) #remember this!
res = ''
l = 1
r = len(s)-1
while l <= r:
mid = (l + r) // 2
dup = has_dup(mid)
if len(dup):
l = mid + 1
res = dup if len(dup) > len(res) else res
else:
r = mid - 1
return res
#time: o(nlogn)
#memory: o(n)Visual
Review 1
Nice problem. I actually came up with a pretty clever and somewhat o(n*n) solution using a trie search…unfortunately this approach results in MLE. I forgot that we must use rabin-karp and binary search for this class of problems. Use memoryview(s.encode()) for o(1) slicing. TODO: learn how to implement rabin-karp rolling hash from scratch.