---
# System prepended metadata

title: 1062. Longest Repeating Substring

---

 # 1062. Longest Repeating Substring
 
 
![](https://hackmd.io/_uploads/r1xh_lS99.png)

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
```python=
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

```python=
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
```