1044. Longest Duplicate Substring

1044

HardTrie and Advanced String SearchBinary search on the answer with Rabin-Karp hashingBinary search on length plus rolling hash

Longest Duplicate Substring

Given a string s, find the longest substring that occurs at least twice in s (occurrences may overlap). Return any such longest duplicated substring, or the empty string if none exists.

Open official problem prompt ↗

In plain English

Return the longest chunk of the string that shows up in two or more (possibly overlapping) places.

Picture it like this

Like finding the longest musical phrase repeated in a song: guess a phrase length, fingerprint every phrase of that length, and see if any fingerprint recurs; then adjust the guessed length.

Example

Input: s = "banana"
Output: "ana"
Why: "ana" appears at index 1 and index 3 and is the longest substring that repeats.

Constraints

2 <= s.length <= 3 * 10^4s consists of lowercase English letters

Pattern lesson

See the pattern, then code

Binary search on length plus rolling hash

↗

Trie and Advanced String Search

Repeated prefix lookup, autocomplete, dictionary search, or many-word matching.. Duplication is monotone in length, so binary search the answer length; for a fixed length, slide a rolling hash across the string and detect a repeated window by a repeated hash in O(n).

New words, made simpleKnow these before the algorithm

Rolling hash: A polynomial fingerprint of a window that updates in O(1) as the window slides.
Binary search on the answer: Searching over the answer value (here, substring length) using a monotone feasibility test.
Hash collision: Two different substrings sharing a hash; a large modulus makes this rare.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Compare all substrings

Far too slow for n up to 3*10^4.

Enumerate every substring and check for a duplicate.

Time O(n^3) or worseSpace O(n^2)

Best choiceBinary search + Rabin-Karp

Exploits monotonicity and O(1) hash updates.

Binary search the length; test feasibility in O(n) with a rolling hash and a hash set.

Time O(n log n)Space O(n)

The rule we keep true

Invariant

During binary search, every length <= the recorded answer is known to have a duplicate, and every length > the current high bound is known not to.

Why this is correct

Reasoning

If some substring of length L repeats, then its length-(L-1) prefix also repeats, so feasibility is monotone in L and binary search is valid; the rolling hash detects a repeat of a fixed length in linear time, and a large prime modulus keeps false collisions negligible.

The algorithm in three movesSay these aloud before coding

1Map characters to integers and pick a large prime modulus

L=3: window hashes of ban,ana,nan,ana

2Binary search the duplicate length between 1 and n-1

'ana' hash repeats at start 1 and 3

3For a candidate length L, roll a polynomial hash over every window and store seen hashes

best = 'ana'

4If a hash repeats, a duplicate of length L exists; record its start and search longer, else search shorter

5Return the best-recorded substring

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Reads='banana', n=6

2 · Asksearch lengths?

3 · Update statelo=1, hi=5

4 · Resultstart binary search

Key takeaway

At length 3 the window 'ana' (indices 1-3) recurs later in the string.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-4Setup
Convert chars to 0-25 codes and fix a base and a large Mersenne prime modulus to limit collisions.
2
Lines 6-18Feasibility check
Roll a polynomial hash over each window of length L; a repeated hash returns the window's start index, else -1.
3
Lines 20-31Binary search
Grow the length on success and shrink on failure, remembering the best start and length found.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

No duplicate at all returns the empty string
Entire string is one repeated character like 'aaaa'
Overlapping duplicates such as 'ana' in 'banana'
Minimum length string of size 2

Common beginner mistakes

Using a small modulus that causes false-positive collisions
Off-by-one when recomputing the rolling hash after the window slides
Returning a start index rather than the substring
Forgetting the empty-string result when start remains -1

Check your understanding

Why is binary search valid for the substring length here?

PyPython 3 · solution.py

Optimal

1class Solution:2    def longestDupSubstring(self, s: str) -> str:3        nums = [ord(c) - ord('a') for c in s]4        base, mod, n = 26, (1 << 61) - 1, len(s)56        def check(L):7            h = 08            for i in range(L):9                h = (h * base + nums[i]) % mod10            seen = {h}11            base_L = pow(base, L, mod)12            for i in range(L, n):13                h = (h * base + nums[i] - nums[i - L] * base_L) % mod14                if h in seen:15                    return i - L + 116                seen.add(h)17            return -11819        lo, hi = 1, n - 120        start, length = -1, 021        while lo <= hi:22            mid = (lo + hi) // 223            pos = check(mid)24            if pos != -1:25                start, length = pos, mid26                lo = mid + 127            else:28                hi = mid - 129        return s[start:start + length] if start != -1 else ""

Time complexityO(n log n) average with rolling hashOptimized

Space complexityO(n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

GoogleAmazonAirbnb

Longest Duplicate Substring

Longest Duplicate Substring

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Trie and Advanced String Search