Problem 35.7 · Advanced String AlgorithmsHard

Longest Duplicate Substring

PatternString Matching (KMP, Z, Rolling Hash)Binary Search on the Answer

What it teaches: Binary search on the length, with a rolling-hash check for each length.

Practise it on judges as “Longest Duplicate Substring”.

In plain words

Find the longest piece of text that appears at least twice. If some length works, every shorter length works too, so you can binary-search on the length. To check one length fast, give each window a number (a rolling hash) and look for two windows with the same number.

Return a longest repeated substring, or "". Example: s = "banana" → "ana".

The problem

Return a longest substring that occurs at least twice (occurrences may overlap), or "" if none. If several have the maximum length, return any (the tests have a unique answer).

Example 1

Input: s = "banana"
Output: "ana"

Constraints

2 ≤ n ≤ 3 × 10⁴

Pattern clues in the wording

→ Longest repeated substring
→ Monotone: a repeat of length L implies one of length L − 1

These clues point to String Matching (KMP, Z, Rolling Hash): Find a pattern inside a text in linear time by reusing what earlier comparisons already proved, or by comparing hashes instead of characters.

Stuck? Take one hint at a time

Solution · starter

import java.util.*;

class Solution {
    public String longestDupSubstring(String s) {
        return "";
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	s = "banana"	"ana"
2	s = "abcd"	""

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Binary search + Rabin-Karp · O(n log n) expected

Binary search + Rabin-Karp

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

find(len) slides a hash over s, storing start positions per hash, and returns a substring whose hash and characters match an earlier one.

▶ Dry run: Binary search on the lengths = "banana"

search(vars)

lo: 1hi: 5best: ""

Step 1/4The answer's length is between 1 and 5. Try the middle, 3.

Approach 1

import java.util.*;

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

    private String find(String s, int len) {
        long MOD = 1_000_000_007L, B = 131, pow = 1, h = 0;
        for (int i = 0; i < len; i++) pow = pow * B % MOD;
        Map<Long, List<Integer>> seen = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            h = (h * B + s.charAt(i)) % MOD;
            if (i >= len) h = ((h - s.charAt(i - len) * pow) % MOD + MOD) % MOD;
            if (i < len - 1) continue;
            int start = i - len + 1;
            List<Integer> starts = seen.computeIfAbsent(h, k -> new ArrayList<>());
            for (int j : starts) if (s.regionMatches(j, s, start, len)) return s.substring(start, start + len);
            starts.add(start);
        }
        return null;
    }
}

Verdict: A suffix array solves it in O(n log n) deterministically, but this is far easier to write.

Before you submit

Edge cases and common mistakes

Test these inputs

No repeats ("")
Overlapping repeats ("aaaa" → "aaa")

Mistakes people make

Trusting a hash match without verifying.

Interview

Follow-up questions

What is the suffix-array approach?

Command Palette

The problem

Approaches

Binary search + Rabin-Karp

Edge cases and common mistakes

Follow-up questions