Longest Duplicate Substring solution and explanation
Google
9 more videos on this problem
Longest Duplicate Substring | TRIE | Rolling Hash | Binary Search | Leetcode #1044Techdose · 29:42 · 44K views
Longest Duplicate Substring | LeetCode 1044 | Rabin Karp AlgorithmKnowledge Center · 33:40 · 11K views
Longest Duplicate Substring | Day 19 | [June LeetCoding Challenge] [Leetcode #1044] [2020]Algorithms Made Easy · 4:21 · 3K views
Longest Duplicate Substring | Rabin Karp Hashing Algo | Leetcode 1044 | Live coding session 🔥🔥🔥Coding Decoded · 14:29 · 2K views
Leetcode - Longest Duplicate Substring (Python)Timothy H Chang · 9:52 · 2K views
【每日一题】1044. Longest Duplicate Substring, 6/19/2020Huifeng Guan · 35:55 · 1K views
LeetCode 1044. Longest Duplicate SubstringHappy Coding · 38:04 · 1K views
Leetcode 1044 Longest Duplicate SubstringRen Zhang · 24:32 · 1K views
Leetcode Longest Duplicate Substring Java SolutionHackerHeap · 20:05 · 674 views
Longest Duplicate Substring | Rolling Hash Robin karp algorithm | Leetcode 1044 | Coders CampCoders Camp · 21:53 · 470 views
The problem
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.
Approach overview
Problem Overview: Given a string s, return the longest substring that appears at least twice. The duplicates can overlap, but the returned substring must be the longest possible repeated sequence. If none exist, return an empty string.
Approach 1: Binary Search with Rolling Hash (Rabin–Karp) (Time: O(n log n), Space: O(n))
This approach combines binary search with a rolling hash to efficiently test substring lengths. Instead of checking every substring pair, you binary search the length L of the duplicate substring. For a given length, compute rolling hashes for all substrings of length L using a sliding window and store them in a hash set. If two substrings produce the same hash, a duplicate of length L exists.
The key insight: if a duplicate substring of length L exists, then duplicates also exist for all lengths smaller than L. That monotonic property makes binary search valid. Each check runs in O(n) using rolling hash updates while sliding across the string. Combined with log n binary search steps, the total complexity becomes O(n log n). This is the most common solution used in competitive programming and interviews.
Approach 2: Suffix Array with Binary Search (Time: O(n log n), Space: O(n))
A more classical string-processing solution uses a suffix array. First generate all suffixes of the string and sort them lexicographically. When suffixes are sorted, duplicate substrings appear as common prefixes between adjacent suffixes. You then compute the longest common prefix (LCP) between neighboring suffixes and track the maximum length.
To accelerate substring length checks, binary search can also be applied on the possible duplicate length while comparing prefixes in the suffix array. Building the suffix array typically takes O(n log n) time with standard algorithms, and scanning for the maximum LCP takes O(n). The memory usage is linear because only arrays for suffix indices and LCP values are stored.
This method avoids hash collisions entirely and relies on deterministic lexicographic ordering. It’s widely used in advanced string processing systems such as text indexing and genome analysis. The downside is implementation complexity compared to rolling hash.
Recommended for interviews: The binary search + rolling hash solution is usually expected. It shows strong understanding of string algorithms, sliding window hashing, and search optimization. A brute-force comparison of all substrings demonstrates the problem structure but runs in O(n^2) or worse. The rolling hash optimization reduces comparisons dramatically and is the practical approach most interviewers want to see.
Approach 1: Binary Search with Rolling Hashing
This approach leverages binary search in conjunction with the Rabin-Karp (rolling hash) algorithm to find the longest duplicate substring within a given string.
We perform binary search on the length of the possible substring, starting from 1 to length of s-1. For each mid-length obtained from the binary search, we use a rolling hash function to hash each substring of length mid. This hash is used to quickly identify duplicates due to its constant time complexity for fixed-length substrings.
class Solution:
def longestDupSubstring(self, s: str) -> str:
def search(length: int) -> str:
MOD = 10000007
BASE = 26
current_hash = 0
base_l = pow(BASE, length, MOD)
seen = set()
for i in range(length):
current_hash = (current_hash * BASE + ord(s[i]) - ord('a')) % MOD
seen.add(current_hash)
for i in range(length, len(s)):
current_hash = ((current_hash * BASE - (ord(s[i - length]) - ord('a')) * base_l) + ord(s[i]) - ord('a')) % MOD
if current_hash in seen:
return s[i - length + 1:i + 1]
seen.add(current_hash)
return ""
left, right = 1, len(s) - 1
result = ""
while left <= right:
mid = left + (right - left) // 2
dup = search(mid)
if dup:
left = mid + 1
result = dup
else:
right = mid - 1
return result
# Example usage:
s = "banana"
solution = Solution()
print(solution.longestDupSubstring(s))import java.util.HashSet;
public class Solution {
private static final int MOD = 10000007;
private static final int BASE = 26;
public String longestDupSubstring(String s) {
int n = s.length();
int left = 0, right = n - 1;
String result = "";
while (left <= right) {
int mid = left + (right - left) / 2;
String dup = findDup(s, mid);
if (!dup.equals("")) {
left = mid + 1;
result = dup;
} else {
right = mid - 1;
}
}
return result;
}
private String findDup(String s, int len) {
HashSet<Integer> seen = new HashSet<>();
long hash = 0, power = 1;
for (int i = 0; i < len; i++) {
hash = (hash * BASE + s.charAt(i) - 'a') % MOD;
if (i < len - 1) power = (power * BASE) % MOD;
}
seen.add((int) hash);
for (int i = len; i < s.length(); i++) {
hash = (hash * BASE - power * (s.charAt(i - len) - 'a') % MOD + MOD) % MOD;
hash = (hash + s.charAt(i) - 'a') % MOD;
if (seen.contains((int) hash)) {
return s.substring(i - len + 1, i + 1);
}
seen.add((int) hash);
}
return "";
}
public static void main(String[] args) {
Solution sol = new Solution();
String s = "banana";
System.out.println(sol.longestDupSubstring(s));
}
}#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;
class Solution {
const int MOD = 10000007;
const int BASE = 26;
public:
string longestDupSubstring(string s) {
int n = s.size();
int left = 1, right = n - 1;
string result = "";
while (left <= right) {
int mid = left + (right - left) / 2;
string dup = findDup(s, mid);
if (!dup.empty()) {
left = mid + 1;
result = dup;
} else {
right = mid - 1;
}
}
return result;
}
string findDup(string &s, int len) {
unordered_set<int> seen;
long long hash = 0, power = 1;
for (int i = 0; i < len; ++i) {
hash = (hash * BASE + (s[i] - 'a')) % MOD;
power = (power * BASE) % MOD;
}
seen.insert(hash);
for (int i = len; i < s.size(); ++i) {
hash = ((hash * BASE - (s[i - len] - 'a') * power % MOD + MOD) % MOD + (s[i] - 'a')) % MOD;
if (seen.count(hash)) {
return s.substr(i - len + 1, len);
}
seen.insert(hash);
}
return "";
}
};
int main() {
Solution sol;
string s = "banana";
cout << sol.longestDupSubstring(s) << endl;
return 0;
}function longestDupSubstring(s) {
const MOD = 10000007;
const BASE = 26;
function search(len) {
let hash = 0,
baseL = 1;
const seen = new Set();
for (let i = 0; i < len; ++i) {
hash = (hash * BASE + (s.charCodeAt(i) - 'a'.charCodeAt(0))) % MOD;
baseL = (i < len - 1) ? (baseL * BASE) % MOD : baseL;
}
seen.add(hash);
for (let i = len; i < s.length; ++i) {
hash = (hash * BASE - (s.charCodeAt(i - len) - 'a'.charCodeAt(0)) * baseL % MOD + MOD) % MOD;
hash = (hash + (s.charCodeAt(i) - 'a'.charCodeAt(0))) % MOD;
if (seen.has(hash)) return s.substring(i - len + 1, i + 1);
seen.add(hash);
}
return "";
}
let left = 0,
right = s.length - 1,
result = "";
while (left <= right) {
const mid = left + ((right - left) >> 1);
const dup = search(mid);
if (dup) {
left = mid + 1;
result = dup;
} else {
right = mid - 1;
}
}
return result;
}
console.log(longestDupSubstring("banana"));#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MOD 10000007
#define BASE 26
unsigned long long rolling_hash(char *s, int start, int len, unsigned long long last_hash, unsigned long long power) {
if (start == 0) {
unsigned long long hash = 0;
for (int i = 0; i < len; ++i) {
hash = (hash * BASE + (s[i] - 'a')) % MOD;
}
return hash;
} else {
last_hash = (BASE * (last_hash - power * (s[start - 1] - 'a')) + (s[start + len - 1] - 'a')) % MOD;
if (last_hash < 0) last_hash += MOD;
return last_hash;
}
}
char *longestDupSubstring(char *s) {
int len = strlen(s);
int left = 0, right = len - 1, start = -1, max_len = 0;
unsigned long long power[len];
power[0] = 1;
for (int i = 1; i < len; ++i) power[i] = (power[i - 1] * BASE) % MOD;
while (left < right) {
int mid = left + (right - left) / 2;
int m = mid + 1;
unsigned long long curr_hash = 0;
unsigned long long seen_hashes[MOD] = {0};
bool found_dup = false;
for (int i = 0; i <= len - m; ++i) {
curr_hash = rolling_hash(s, i, m, curr_hash, power[m - 1]);
if (seen_hashes[curr_hash % MOD] != 0) {
found_dup = true;
start = seen_hashes[curr_hash % MOD] - 1;
max_len = m;
break;
} else {
seen_hashes[curr_hash % MOD] = i + 1;
}
}
if (found_dup) left = mid + 1;
else right = mid;
}
if (max_len > 0) {
char *res = (char *)malloc(sizeof(char) * (max_len + 1));
strncpy(res, s + start, max_len);
res[max_len] = '\0';
return res;
}
return "";
}
int main() {
char *s = "banana";
printf("%s\n", longestDupSubstring(s));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
static int MOD = 10000007;
static int BASE = 26;
public string LongestDupSubstring(string s) {
int n = s.Length;
int left = 1, right = n - 1;
string result = "";
while (left <= right) {
int mid = left + (right - left) / 2;
string dup = FindDup(s, mid);
if (dup.Length > 0) {
left = mid + 1;
result = dup;
} else {
right = mid - 1;
}
}
return result;
}
private string FindDup(string s, int len) {
var seen = new HashSet<int>();
long hash = 0, power = 1;
for (int i = 0; i < len; i++) {
hash = (hash * BASE + (s[i] - 'a')) % MOD;
if (i < len - 1) power = (power * BASE) % MOD;
}
seen.Add((int) hash);
for (int i = len; i < s.Length; i++) {
hash = (hash * BASE - power * (s[i - len] - 'a') % MOD + MOD) % MOD;
hash = (hash + (s[i] - 'a')) % MOD;
if (seen.Contains((int)hash)) {
return s.Substring(i - len + 1, len);
}
seen.Add((int) hash);
}
return "";
}
public static void Main() {
Solution solution = new Solution();
Console.WriteLine(solution.LongestDupSubstring("banana"));
}
}This Python solution utilizes binary search to find the longest duplicate substring. It generates hashes for substrings and uses a set to detect duplicates efficiently, returning the longest one found.
Time Complexity: O(n log n). The binary search performs in O(log n) time, and each hashing operation per length is O(n).
Space Complexity: O(n) due to storage of hash values in a set.
Approach 2: Suffix Array with Binary Search
This method involves constructing a suffix array from the input string and then performing binary search on the suffixes to find the longest duplicate substring.
Using suffix arrays, we can efficiently sort and group starting indices of the given string. Then, by employing binary search, we determine the largest-length substring that repeats. The Longest Common Prefix (LCP) array helps in assessing the similarity of suffixes at each binary search step.
class Solution:
def longestDupSubstring(self, s: str) -> str:
suffixes = [s[i:] for i in range(len(s))]
suffixes.sort()
def common_prefix_length(s1, s2):
min_len = min(len(s1), len(s2))
for i in range(min_len):
if s1[i] != s2[i]:
return i
return min_len
result = ""
for i in range(1, len(s)):
len_common = common_prefix_length(suffixes[i - 1], suffixes[i])
if len_common > len(result):
result = suffixes[i][:len_common]
return result
# Example usage:
s = "banana"
solution = Solution()
print(solution.longestDupSubstring(s))import java.util.Arrays;
public class Solution {
public String longestDupSubstring(String s) {
int n = s.length();
String[] suffixes = new String[n];
for (int i = 0; i < n; i++) {
suffixes[i] = s.substring(i);
}
Arrays.sort(suffixes);
String result = "";
for (int i = 1; i < n; i++) {
int len = commonPrefixLength(suffixes[i - 1], suffixes[i]);
if (len > result.length()) {
result = suffixes[i].substring(0, len);
}
}
return result;
}
private int commonPrefixLength(String s1, String s2) {
int len = 0, limit = Math.min(s1.length(), s2.length());
while (len < limit && s1.charAt(len) == s2.charAt(len)) {
len++;
}
return len;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.longestDupSubstring("banana"));
}
}#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
string longestDupSubstring(string s) {
int n = s.size();
vector<string> suffixes(n);
for (int i = 0; i < n; i++) {
suffixes[i] = s.substr(i);
}
sort(suffixes.begin(), suffixes.end());
string result = "";
for (int i = 1; i < n; i++) {
string &s1 = suffixes[i - 1], &s2 = suffixes[i];
int length = 0, limit = min(s1.size(), s2.size());
while (length < limit && s1[length] == s2[length]) {
length++;
}
if (length > result.size()) {
result = s1.substr(0, length);
}
}
return result;
}
int main() {
cout << longestDupSubstring("banana") << endl;
return 0;
}function longestDupSubstring(s) {
let suffixes = Array.from({ length: s.length }, (_, i) => s.substring(i));
suffixes.sort();
function commonPrefix(s1, s2) {
let i = 0;
while (i < s1.length && s1[i] === s2[i]) ++i;
return i;
}
let result = "";
for (let i = 1; i < suffixes.length; i++) {
let len = commonPrefix(suffixes[i - 1], suffixes[i]);
if (len > result.length) {
result = suffixes[i].slice(0, len);
}
}
return result;
}
console.log(longestDupSubstring("banana"));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int compare(const void *a, const void *b) {
return strcmp(*(const char **)a, *(const char **)b);
}
char *longestDupSubstring(char *s) {
int n = strlen(s);
char **suffixes = (char **)malloc(n * sizeof(char *));
for (int i = 0; i < n; ++i) {
suffixes[i] = s + i;
}
qsort(suffixes, n, sizeof(char *), compare);
int max_len = 0;
char *result = "";
for (int i = 1; i < n; ++i) {
int len = 0;
while (suffixes[i][len] == suffixes[i - 1][len]) len++;
if (len > max_len) {
max_len = len;
result = (char *)malloc((len + 1) * sizeof(char));
strncpy(result, suffixes[i], len);
result[len] = '\0';
}
}
free(suffixes);
return result;
}
int main() {
char *s = "banana";
printf("%s\n", longestDupSubstring(s));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public string LongestDupSubstring(string s) {
int n = s.Length;
var suffixes = new List<string>();
for (int i = 0; i < n; i++) {
suffixes.Add(s.Substring(i));
}
suffixes.Sort();
string result = "";
for (int i = 1; i < n; i++) {
int len = CommonPrefixLength(suffixes[i - 1], suffixes[i]);
if (len > result.Length) {
result = suffixes[i].Substring(0, len);
}
}
return result;
}
private int CommonPrefixLength(string s1, string s2) {
int length = 0;
while (length < s1.Length && length < s2.Length && s1[length] == s2[length]) {
length++;
}
return length;
}
public static void Main() {
Solution solution = new Solution();
Console.WriteLine(solution.LongestDupSubstring("banana"));
}
}This Python solution generates and sorts the suffix array, then finds the longest common prefix of each consecutive suffix by comparing characters, revealing the longest repeated substring.
Time Complexity: O(n^2 log n), as sorting n suffixes each up to length n is expensive.
Space Complexity: O(n^2), due to full storage of each suffix.
Approach 3: Default Approach
func longestDupSubstring(s string) string {
base, n := 131, len(s)
p := make([]int64, n+10)
h := make([]int64, n+10)
p[0] = 1
for i := 0; i < n; i++ {
p[i+1] = p[i] * int64(base)
h[i+1] = h[i]*int64(base) + int64(s[i])
}
check := func(l int) string {
vis := make(map[int64]bool)
for i := 1; i+l-1 <= n; i++ {
j := i + l - 1
t := h[j] - h[i-1]*p[j-i+1]
if vis[t] {
return s[i-1 : j]
}
vis[t] = true
}
return ""
}
left, right := 0, n
ans := ""
for left < right {
mid := (left + right + 1) >> 1
t := check(mid)
if len(t) > 0 {
left = mid
ans = t
} else {
right = mid - 1
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Binary Search with Rolling Hashing | Time Complexity: O(n log n). The binary search performs in O(log n) time, and each hashing operation per length is O(n). Space Complexity: O(n) due to storage of hash values in a set. |
| Suffix Array with Binary Search | Time Complexity: O(n^2 log n), as sorting n suffixes each up to length n is expensive. Space Complexity: O(n^2), due to full storage of each suffix. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Comparison | O(n^3) | O(1) | Conceptual understanding or very small strings |
| Binary Search + Rolling Hash | O(n log n) | O(n) | Best practical solution for interviews and competitive programming |
| Suffix Array + LCP | O(n log n) | O(n) | When using advanced string-processing structures or deterministic comparisons |
Frequently asked questions
Is Longest Duplicate Substring easy or hard?
Longest Duplicate Substring is classified as a hard problem because it requires combining multiple algorithmic concepts such as binary search, rolling hash, or suffix arrays. Efficient solutions must avoid naive substring comparisons, which quickly become too slow for large inputs.
How to solve Longest Duplicate Substring in O(n)?
True O(n) solutions exist using advanced suffix array or suffix tree algorithms with linear-time construction and longest common prefix processing. These techniques are complex and rarely expected in interviews. Most practical implementations use O(n log n) time with binary search and rolling hash.
What is the best approach for Longest Duplicate Substring?
Binary search combined with rolling hash (Rabin–Karp) is the most practical approach. It searches for the maximum substring length while verifying duplicates using hash values in O(n) time per check. The overall complexity becomes O(n log n) with O(n) extra space. This solution is widely used in coding interviews and competitive programming.
Is Longest Duplicate Substring asked at Google/Amazon/Meta?
Longest Duplicate Substring is considered a hard string problem and appears in interviews at companies that test advanced algorithmic knowledge. Variants involving rolling hash, suffix arrays, or longest repeated substring logic have been reported in interviews at companies like Google and Amazon.
What data structure is used in Longest Duplicate Substring?
Common structures include hash sets for storing rolling hash values, arrays for prefix hashes and powers, and suffix arrays for lexicographic ordering of suffixes. These structures enable efficient substring comparison without directly comparing characters repeatedly.
What is the time complexity of Longest Duplicate Substring?
The optimal solutions run in O(n log n) time. Binary search over substring length requires log n iterations, and each iteration checks duplicates using rolling hash in O(n). Suffix array based approaches also run in roughly O(n log n) time depending on the construction algorithm.
Longest Duplicate Substring Python or Java solution approach?
Both Python and Java solutions typically implement binary search on substring length with a rolling hash (Rabin–Karp). A sliding window computes hash values for substrings of length L, and duplicates are detected using a hash set. This approach runs in O(n log n) time and O(n) space.