Longest Duplicate Substring — Binary Search and Rabin-Karp Rolling Hash

Problem Statement#

Given a string s, return the longest substring that occurs at least twice. Occurrences may overlap. If none exists, return the empty string.

Constraints:

• 2 <= len(s) <= 3 * 10^4
• s contains only lowercase English letters

Input:  s = "banana"
Output: "ana"
 
Input:  s = "abcd"
Output: ""
 
Input:  s = "aaaa"
Output: "aaa"

Why This Problem Matters#

LeetCode 1044 is a Google, Amazon, and Meta favourite. It earns its Hard rating by demanding two ideas work in tandem: binary search on the answer length and a rolling hash for O(1) substring comparison. Brute force is O(n^3) and times out. The interviewer is checking whether you recognise the monotone predicate and can implement Rabin-Karp without subtle modular bugs.

The Core Insight#

Two observations unlock the problem:

• If a duplicate of length L exists, a duplicate of every length less than L also exists (just take a prefix). The predicate "has a duplicate of length L" is monotone, so binary search the largest L in [1, n-1].
• Comparing every pair of length-L substrings is O(n) per pair. Replace this with a rolling hash — a polynomial hash where each substring fingerprint is computed in O(1) from the previous one — and store fingerprints in a hash set. The first collision flags a duplicate.

Use a large prime modulus (for example 2^63 - 1 in Python, or a 2^53-safe prime in JavaScript) and a base of 26 or 31. To guard against rare hash collisions, when you find a collision, verify the substring slice equals the stored one.

Visual Dry Run#

For s = "banana", n = 6, search L in [1, 5].

Solution (Optimal)#

class Solution:
    def longestDupSubstring(self, s: str) -> str:
        n = len(s)
        nums = [ord(c) - ord('a') for c in s]
        base, mod = 26, (1 << 61) - 1
 
        def has_dup(length: int) -> int:
            if length == 0:
                return -1
            h = 0
            power = pow(base, length, mod)
            for i in range(length):
                h = (h * base + nums[i]) % mod
            seen = {h: 0}
            for start in range(1, n - length + 1):
                h = (h * base - nums[start - 1] * power + nums[start + length - 1]) % mod
                if h in seen:
                    prev = seen[h]
                    if s[prev:prev + length] == s[start:start + length]:
                        return start
                else:
                    seen[h] = start
            return -1
 
        lo, hi, start, best = 1, n - 1, -1, 0
        while lo <= hi:
            mid = (lo + hi) // 2
            idx = has_dup(mid)
            if idx != -1:
                start, best = idx, mid
                lo = mid + 1
            else:
                hi = mid - 1
        return s[start:start + best] if start != -1 else ""

var longestDupSubstring = function(s) {
    const n = s.length;
    const nums = new Array(n);
    for (let i = 0; i < n; i++) nums[i] = s.charCodeAt(i) - 97;
    const base = 26n;
    const mod = (1n << 61n) - 1n;
 
    const hasDup = (length) => {
        if (length === 0) return -1;
        let h = 0n;
        let power = 1n;
        for (let i = 0; i < length; i++) power = (power * base) % mod;
        for (let i = 0; i < length; i++) h = (h * base + BigInt(nums[i])) % mod;
        const seen = new Map();
        seen.set(h, 0);
        for (let start = 1; start <= n - length; start++) {
            h = (h * base - BigInt(nums[start - 1]) * power + BigInt(nums[start + length - 1])) % mod;
            if (h < 0n) h += mod;
            if (seen.has(h)) {
                const prev = seen.get(h);
                if (s.slice(prev, prev + length) === s.slice(start, start + length)) return start;
            } else {
                seen.set(h, start);
            }
        }
        return -1;
    };
 
    let lo = 1, hi = n - 1, start = -1, best = 0;
    while (lo <= hi) {
        const mid = (lo + hi) >> 1;
        const idx = hasDup(mid);
        if (idx !== -1) { start = idx; best = mid; lo = mid + 1; }
        else hi = mid - 1;
    }
    return start === -1 ? "" : s.slice(start, start + best);
};

Time: O(n log n) average Space: O(n) for the hash set

Common Mistakes#

• Forgetting to verify the actual substring on a hash collision — random hash collisions can produce wrong answers without verification.
• Using too small a modulus, dramatically increasing collision rates and slowing down verification.
• Off-by-one in the rolling hash update — the term being removed is nums[start - 1] * base^length, not nums[start - 1].
• In JavaScript, doing arithmetic with regular numbers instead of BigInt — overflow corrupts the hash.
• Skipping binary search and trying every length linearly, which lifts the run time to O(n^2 log n).

Interview Tips#

• Justify why the predicate "duplicate of length L exists" is monotone — that justifies binary search.
• Describe rolling hash as a polynomial fingerprint and explicitly mention modulus and base.
• Mention double hashing or substring verification as collision defences.
• If you have time, contrast with the suffix-array approach which is O(n log n) deterministic but more complex to code.

Follow-up Questions#

• Return all longest duplicate substrings, not just one.
• Solve when the alphabet is unicode — switch the base and the alphabet mapping.
• Solve in O(n) using a suffix automaton or suffix array with LCP.
• Find the longest substring that appears at least k times.
• Apply the same template to longest repeated DNA sequence (LeetCode 187).

Key Takeaways#

• Binary search the answer length because the duplicate property is monotone in L.
• Rolling hash compares substrings in O(1) per slide using the previous fingerprint.
• Always verify on collision to defend against rare modular collisions.
• A 2^61-1 modulus with base 26 or 31 keeps collisions rare on lowercase strings.
• Time is O(n log n) average; space is O(n) for the seen-set per candidate length.
• The same pattern solves repeated DNA sequences and longest common substring.
• Practising Rabin-Karp here pays off in any interview that touches substring search.