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 * 104sconsists 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]
set.add(tmp>
}
return [false, '']
}
Input
s = "banana"
Output
"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
seen.add(cur)
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]
Input
s = "banana"
Output
"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>();
seen.Add(h);
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;
seen.Add(h);
}
return -1;
}
}
}
Input
s = "banana"
Output
"ana"