Longest Duplicate Substring

HardBinary Search · Rolling Hash (Rabin–Karp)🧩 String Matching LeetCode #1044 ↗Updated Oct 30, 2026

Problem

Given a string s, return any substring that occurs at least twice (occurrences may overlap) and is as long as possible. If no substring repeats, return the empty string.

Inputs = "banana"Output"ana"

Inputs = "abcd"Output""

Inputs = "aaaa"Output"aaa"

2 ≤ s.length ≤ 3 · 10⁴ · lowercase English letters · any valid longest answer is accepted

Try it yourself

Java

class Solution {
    public String longestDupSubstring(String s) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Repetition is monotone in length: if some length-L substring repeats, so does its length-(L−1) prefix. Binary search on L, and test each L in O(n) by sliding a rolling hash over all windows.

PatternString Matching

Instinct Find a pattern in a text, or a prefix that is also a suffix, faster than O(n·m) - reach for the KMP prefix function or a rolling hash.

Memory hack KMP remembers borders, Rabin-Karp compares fingerprints - neither one re-reads text it has already seen.

Open the String Matching guide →

Approaches

Brute ForceEvery Length, Longest First

Time O(n³)Space O(n²)

For L = n-1 down to 1, put every length-L substring in a hash set; the first collision is a repeat of the largest possible length, so return it immediately.

Java

public String longestDupSubstring(String s) {
    int n = s.length();
    for (int len = n - 1; len > 0; len--) {
        Set<String> seen = new HashSet<>();
        for (int i = 0; i + len <= n; i++) {
            String sub = s.substring(i, i + len);
            if (!seen.add(sub)) return sub;
        }
    }
    return "";
}

Straightforward, but up to n lengths × n substrings × O(L) hashing each.

BetterBinary Search on Length + HashSet of Substrings

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

Because “a length-L repeat exists” is true for all L up to the answer and false after, binary search the length. Each probe still builds every length-L substring, so a probe is O(n·L).

Java

public String longestDupSubstring(String s) {
    int lo = 1, hi = s.length() - 1;
    String best = "";
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        String dup = findRepeat(s, mid);
        if (dup != null) { best = dup; lo = mid + 1; }
        else hi = mid - 1;
    }
    return best;
}

private String findRepeat(String s, int len) {
    Set<String> seen = new HashSet<>();
    for (int i = 0; i + len <= s.length(); i++) {
        String sub = s.substring(i, i + len);
        if (!seen.add(sub)) return sub;
    }
    return null;
}

Cuts the number of lengths to log n, but materialising substrings is still too slow.

OptimalBinary Search + Rabin–Karp Rolling Hash

Time O(n log n) expectedSpace O(n)

Same binary search, but each probe slides a window hash in O(1) per step: drop the leading char (−c·B^L) and add the new one. Two moduli keep collisions rare, and any hash hit is confirmed with regionMatches, so the answer is always correct.

Java

private static final long M1 = 1_000_000_007L, M2 = 1_000_000_009L, B = 131;

public String longestDupSubstring(String s) {
    int lo = 1, hi = s.length() - 1, bestStart = 0, bestLen = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int start = findRepeat(s, mid);
        if (start >= 0) { bestStart = start; bestLen = mid; lo = mid + 1; }
        else hi = mid - 1;
    }
    return s.substring(bestStart, bestStart + bestLen);
}

// Start index of a second occurrence of some length-len substring, or -1
private int findRepeat(String s, int len) {
    int n = s.length();
    long h1 = 0, h2 = 0, p1 = 1, p2 = 1;
    for (int i = 0; i < len; i++) {
        h1 = (h1 * B + s.charAt(i)) % M1;
        h2 = (h2 * B + s.charAt(i)) % M2;
        p1 = p1 * B % M1;
        p2 = p2 * B % M2;
    }
    Map<Long, List<Integer>> seen = new HashMap<>();
    for (int i = 0; ; i++) {
        List<Integer> starts = seen.computeIfAbsent(h1 * M2 + h2, k -> new ArrayList<>());
        for (int j : starts) {
            if (s.regionMatches(j, s, i, len)) return i; // confirm: no false positive
        }
        starts.add(i);
        if (i + len == n) return -1;
        char out = s.charAt(i), in = s.charAt(i + len);
        h1 = ((h1 * B - out * p1 % M1 + M1) % M1 + in) % M1;
        h2 = ((h2 * B - out * p2 % M2 + M2) % M2 + in) % M2;
    }
}

Dry runs = "banana"

o occurrence start changed

lo=1,hi=5
b

a

n

a

n

a

search length range
L=3
b

a
o
n

a
o
n

a

ana twice → lo=4
L=4
b

a

n

a

n

a

bana,anan,nana: none
done
b

a

n

a

n

a

hi=3 < lo → ana ✔

Each probe is O(n) expected — fast enough for n = 3·10⁴.

Pro tip

Always verify a hash hit (or use two moduli) — strings like Thue–Morse break single 64-bit overflow hashes.

At a glance

Level	Approach	Time	Space
Brute Force	Every Length, Longest First	`O(n³)`	`O(n²)`
Better	Binary Search on Length + HashSet of Substrings	`O(n² log n)`	`O(n²)`
Optimal	Binary Search + Rabin–Karp Rolling Hash	`O(n log n) expected`	`O(n)`

Common pitfalls

Linear search over L from long to short with hashing — O(n²), times out.
Trusting a single hash without verification — collisions give wrong answers.
Negative values when removing the outgoing char — add the modulus before %.

Interview tips

Spot the monotone predicate first; it justifies binary search on the answer.
Explain the rolling update formula and the role of B^L.
Mention the suffix array + LCP solution as the deterministic O(n log n) alternative.

Pattern

Binary search on answer + Rabin–Karp → find the longest length L for which some window-of-length-L property holds.

My notes saved in this browser