# 1062. Longest Repeating Substring


Constraints:

1 <= s.length <= 2000
s consists of lowercase English letters.

similar: https://hackmd.io/@y56/H1p9Gdeac

## subtask 1: return T/F if there exist dup substrings of length L

def has_dup(L):
    check all substring of length L: whether there are dups among them
    return T/F

1. Linear-time in one slice + hashset of already seen strings.
O((N−L)L) time complexity and huge space consumption in the case of large strings.

2. Linear-time in one slice + hashset of hashes of already seen strings.
O((N−L)L) time complexity and moderate space consumption even in the case of large strings.

3. Rabin-Karp = constant-time in one slice + hashset of hashes of already seen strings.
Hashes are computed with the **rolling hash algorithm**.
O(N−L) time complexity and moderate space consumption even in the case of large strings.

## subtask 2: find largest L
use binary search to find largest L having dups

## to combine

remember to let has_dup(0) as False

l = 1
r = N-1 # N is len(input_string)
while l <= r: # break at l+1 == r
    mid = (l+r)//2 # length of ask
    if has_dups(mid):
        l = mid + 1# keep l as unknown
    else:
        r = mid - 1 # keep r as dups
  
return l - 1 # r