## Algorithm

Problem Name: 1044. Longest Duplicate Substring

Given a string `s`, consider all duplicated substrings: (contiguous) substrings of s that occur 2 or more times. The occurrences may overlap.

Return any duplicated substring that has the longest possible length. If `s` does not have a duplicated substring, the answer is `""`.

Example 1:

```Input: s = "banana"
Output: "ana"
```

Example 2:

```Input: s = "abcd"
Output: ""
```

Constraints:

• `2 <= s.length <= 3 * 104`
• `s` consists of lowercase English letters.

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const longestDupSubstring = function(s) {
const n = s.length
let l = 0, r = n, res = ''
while(l < r) {
const mid = (l + r + 1) >> 1
const [chk, str] = valid(s, mid)
if(chk) {
l = mid
res = str
} else {
r = mid - 1
}
}
return res
};

function valid(s, len) {
const set = new Set()
for(let i = 0, n = s.length; i <= n - len; i++) {
const tmp = s.substr(i, len)
if(set.has(tmp)) return [true, tmp]
}

return [false, '']
}
``````
Copy The Code &

Input

cmd
s = "banana"

Output

cmd
"ana"

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
from functools import reduce
class Solution:
def longestDupSubstring(self, S: str) -> str:
A = [ord(c) - ord('a') for c in S]
mod = 2**63 - 1

def test(L):
p = pow(26, L, mod)
cur = reduce(lambda x, y: (x * 26 + y) % mod, A[:L], 0)
seen = {cur}
for i in range(L, len(S)):
cur = (cur * 26 + A[i] - A[i - L] * p) % mod
if cur in seen: return i - L + 1
res, lo, hi = 0, 0, len(S)
while lo < hi:
mi = (lo + hi + 1) // 2
pos = test(mi)
if pos:
lo = mi
res = pos
else:
hi = mi - 1
return S[res:res + lo]
``````
Copy The Code &

Input

cmd
s = "banana"

Output

cmd
"ana"

### #3 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections.Generic;

namespace LeetCode
{
public class _1044_LongestDuplicateSubstring
{
private const int ALPHABET = 26;
private long modulus = (long)Math.Pow(2, 32);

public string LongestDupSubstring(string S)
{
var n = S.Length;
int left = 1, right = n;
var result = string.Empty;
while (left  < = right)
{
var mid = left + (right - left) / 2;
var start = Search(S.ToCharArray(), mid);
if (start != -1)
{
result = S.Substring(start, mid);
left = mid + 1;
}
else right = mid - 1;
}

return result;
}

private int Search(char[] chArray, int targetLength)
{
var n = chArray.Length;

long h = 0;
for (int i = 0; i  <  targetLength; i++)
h = (h * ALPHABET + chArray[i] - 'a') % modulus;

var seen = new HashSet < long>();

long aL = 1;
for (int i = 1; i  < = targetLength; i++)
aL = (aL * ALPHABET) % modulus;

for (int start = 0; start  <  n - targetLength; start++)
{
h = (h * ALPHABET - (chArray[start] - 'a') * aL % modulus + modulus) % modulus;
h = (h + chArray[start + targetLength] - 'a') % modulus;
if (seen.Contains(h)) return start + 1;
}

return -1;
}
}
}
``````
Copy The Code &

Input

cmd
s = "banana"

Output

cmd
"ana"