Longest Duplicate Substring (LeetCode 1044)

The problem

Given a string s of lowercase letters, return the longest substring that occurs at least twice (the occurrences may overlap). If no substring repeats, return "". Any one longest answer is accepted.

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

"ana" starts at index 1 and again at index 3; the two copies overlap. No substring of length 4 repeats.

How to think about it

Start with brute force. For each length L from long to short, put every window of length L in a set and stop at the first repeat. Each length costs O(n · L) for slicing and hashing, and there are n lengths, so O(n³) in the worst case. With n = 3 × 10⁴, hopeless.

First insight: the answer is monotonic, so binary-search its length. If some substring of length L repeats, then its first L − 1 characters repeat too. So “a duplicate of length L exists” is true up to some point and false after it. Binary search finds that point in O(log n) checks, the “binary search on the answer” idea from Lesson 10.

Second insight: check one length in O(n) with a rolling hash. For a fixed L, you need to know whether any two windows are equal. Hash each window as a number in base 26. Moving the window one step right, drop the leftmost letter and add the new one in O(1): h = h·26 − (old letter)·26ᴸ + (new letter), all mod a big prime. Put the hashes in a set; a repeat means a duplicate (barring a collision). This is Rabin-Karp.

Which pattern is this? Binary search on the answer combined with Rabin-Karp. The tell is “longest substring with a property that’s monotonic in length”. A suffix array also solves it in O(n log n), but is far harder to write in an interview.

Approach

1. Map letters to numbers 0–25. Choose base = 26 and a large modulus.
2. search(L): hash the first window, put it in seen, then roll the window across s. If a hash is already in seen, return that start index. Otherwise return -1.
3. Binary-search L between 1 and n. If search(mid) finds a start, record it and try longer (lo = mid + 1). If not, try shorter (hi = mid - 1).
4. When the search ends, hi is the longest length that worked. Return s[start:start + hi], or "" if hi is 0.

Solution

def longestDupSubstring(s):
    n = len(s); nums = [ord(c) - 97 for c in s]; MOD = 2**63 - 1; base = 26
    def search(L):
        if L == 0:
            return 0
        h = 0
        for i in range(L):
            h = (h * base + nums[i]) % MOD
        seen = {h}; baseL = pow(base, L, MOD)
        for i in range(1, n - L + 1):
            # roll: drop nums[i-1] from the left, add nums[i+L-1] on the right
            h = (h * base - nums[i - 1] * baseL + nums[i + L - 1]) % MOD
            if h in seen:
                return i
            seen.add(h)
        return -1
    lo, hi, start = 1, n, 0
    while lo <= hi:
        mid = (lo + hi) // 2; pos = search(mid)
        if pos != -1:
            start = pos; lo = mid + 1       # found one this long → try longer
        else:
            hi = mid - 1                     # too long → shorten
    return s[start:start + hi] if hi > 0 else ""
# longestDupSubstring("banana") -> "ana"

Dry run

On s = "banana" (n = 6):

The answer is s[3:6] = "ana".

Complexity

• Time: O(n log n) on average. About log n binary-search steps, each an O(n) rolling-hash pass with O(1) set operations.
• Space: O(n). For the hash set and the number list.

Edge cases and pitfalls

• No repeat ("abcd"): every search fails, hi ends at 0, return "".
• All one letter ("aaaaa"): the answer is "aaaa"; overlapping copies count.
• Hash collisions. This version trusts the hash without comparing the actual substrings, so a collision could, in theory, report a false duplicate. A production version compares the strings on a hash hit, or uses two independent hashes. Mention this.
• Negative values in the roll. Python’s % always returns a non-negative result, but in Java or C++ you must add MOD before taking the remainder.
• Returning s[start:start + mid] after the loop is a bug: mid is the last length tried, not the last that worked. Use hi.

We cross-checked the returned length against a brute force on 300 random short strings.

Related problems

• Repeated DNA Sequences (LeetCode 187): the seen-set check for one fixed length.
• Koko Eating Bananas (LeetCode 875): the same binary search on the answer with a feasibility check.
• Split Array Largest Sum (LeetCode 410): binary search on the answer with a greedy check.