38 · Segment Trees, Fenwick & String Matching

#1044 Longest Duplicate Substring

frequently reported atByteDance / TikTok Google Amazon Goldman Sachs Meta

the problem

In plain words

Return any duplicated substring (one that occurs at least twice, occurrences may overlap) with the maximum possible length. Return "" if there is none.

in s = "banana"

out "ana"

in s = "abcd"

out ""

2 ≤ s.length ≤ 3·10⁴
Lowercase English letters

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBinary search on the answer Rolling hash (Rabin–Karp)

If a duplicate of length L exists, one of length L−1 does too (drop a character). That monotonicity lets you binary search the length; a rolling hash checks one length in O(n).

solutions

From brute force to optimal

From the longest length down, put every substring in a HashSet; the first repeat wins.

For len = n−1 down to 1.
Add each substring of that length to a set; a failed add is a duplicate.

timeO(n³)

n lengths × n substrings × O(len) to build and hash each.

spaceO(n²)

One length's substrings stored at a time: up to n strings of up to n chars.

javajava.util.*

1class Solution {2    public String longestDupSubstring(String s) {3        int n = s.length();4        for (int len = n - 1; len > 0; len--) {           // longest length first5            Set<String> seen = new HashSet<>();6            for (int i = 0; i + len <= n; i++) {7                String sub = s.substring(i, i + len);8                if (!seen.add(sub)) return sub;            // add() is false when already present9            }10        }11        return "";12    }13}

Binary search the length; check each length with a set of real substrings.

lo = 1, hi = n − 1.
If a duplicate of length mid exists → record it, go longer; else go shorter.

timeO(n² log n)

log n lengths × n substrings × O(n) each.

spaceO(n²)

The substrings in the set.

javajava.util.*

1class Solution {2    public String longestDupSubstring(String s) {3        String best = "";4        int lo = 1, hi = s.length() - 1;5        while (lo <= hi) {                    // a duplicate of length L implies one of length L-16            int mid = lo + (hi - lo) / 2;7            String dup = findDuplicate(s, mid);8            if (dup != null) { best = dup; lo = mid + 1; }9            else hi = mid - 1;10        }11        return best;12    }13 14    private String findDuplicate(String s, int len) {15        Set<String> seen = new HashSet<>();16        for (int i = 0; i + len <= s.length(); i++) {17            String sub = s.substring(i, i + len);  // O(len) to build and to hash18            if (!seen.add(sub)) return sub;19        }20        return null;21    }22}

Same binary search, but store rolling hashes (with start indices to verify collisions).

For a length len: hash the first window, then roll across s.
Map hash → list of starts; on a hit, confirm with regionMatches.
Binary search on len as before.

timeO(n log n) expected

log n lengths × O(n) rolling per length; verification is rare except for true matches, which end the scan.

spaceO(n)

At most n hashes and starts per length.

javajava.util.*

1class Solution {2    private static final long MOD = 1_000_000_007L, BASE = 131;3 4    public String longestDupSubstring(String s) {5        int lo = 1, hi = s.length() - 1, bestStart = -1, bestLen = 0;6        while (lo <= hi) {7            int mid = lo + (hi - lo) / 2;8            int start = findDuplicate(s, mid);9            if (start >= 0) { bestStart = start; bestLen = mid; lo = mid + 1; }10            else hi = mid - 1;11        }12        return bestStart < 0 ? "" : s.substring(bestStart, bestStart + bestLen);13    }14 15    /** Start of a substring of length len that appeared earlier, or -1. */16    private int findDuplicate(String s, int len) {17        long high = 1, hash = 0;18        for (int i = 1; i < len; i++) high = high * BASE % MOD;          // BASE^(len-1)19        for (int i = 0; i < len; i++) hash = (hash * BASE + s.charAt(i)) % MOD;20        Map<Long, List<Integer>> seen = new HashMap<>();21        seen.computeIfAbsent(hash, k -> new ArrayList<>()).add(0);22        for (int i = 1; i + len <= s.length(); i++) {23            hash = (hash - s.charAt(i - 1) * high % MOD + MOD) % MOD;  // drop the left char24            hash = (hash * BASE + s.charAt(i + len - 1)) % MOD;        // add the right char25            List<Integer> starts = seen.computeIfAbsent(hash, k -> new ArrayList<>());26            for (int j : starts)27                if (s.regionMatches(j, s, i, len)) return i;  // same hash AND same text28            starts.add(i);29        }30        return -1;31    }32}

in the room

How to say it in the interview

talk track

Spot the monotonic property first, then binary search the length — that's half the solution.
Then: "checking one length with real strings is O(n²); a rolling hash makes it O(n)."
Mention collisions and how you verify.

traps

Skipping verification and returning a substring that only hashes the same.
int overflow in hash arithmetic — use long.

what they ask next

Follow-ups

Deterministic O(n log n) or O(n)?

A suffix array with the LCP array: the answer is the maximum LCP of adjacent suffixes.

before you submit

Edge cases to test

No repeated character → ""
Overlapping copies count: "aaaaa" → "aaaa"
Hash collisions: two different substrings with the same hash must not be reported
Two equal letters, "aa" → "a"

practise next