https://leetcode.com/problems/longest-duplicate-substring/
Still work in progress.
current verion fails due to time limit.
class Solution:
# 2506ms
def longestDupSubstring(self, s: str) -> str:
def find_duplicated(s, k):
for i in range(len(s) - k + 1):
substr = s[i:i+k]
if s.find(substr, i+1) != -1:
return substr
return ''
# binary search of length of the answer
lower = 0
upper = len(s)
ans = ''
while lower < upper:
print (lower, upper)
middle = (lower + upper) // 2
dup = find_duplicated(s, middle)
# if not found, lower the `upper` to `middle`
# Otherwise, raise the `lower` to `middle` + 1
if dup == "":
upper = middle
else:
lower = middle + 1
ans = dup
return ans