Longest Duplicate Substring

Longest Duplicate Substring is a beautiful "two algorithms stacked on top of each other" problem. It binary searches over a length, and uses a rolling hash (Rabin-Karp) to answer each yes/no question fast. Master it and you understand both monotonic binary search and string hashing at once.

The slow way first

The obvious idea: check every possible substring and see if it shows up elsewhere. There are about O(n²) substrings and comparing each one costs O(n), so this is roughly O(n³) — far too slow for a long string.

The question to ask: what makes this hard? Two things at once — we do not know the answer length, and for a given length, checking for a repeat naively is expensive. We attack each separately.

The idea: binary search the length, hash to check it

Here is the key insight: if a duplicate of length L exists, then a duplicate of every shorter length exists too (just take a prefix of it). That makes "is there a duplicate of length L?" a monotonic yes/no — true for small L, false for large L — so we can binary search the largest L that still answers yes.

To answer one question — is there any repeated substring of exactly length L? — slide a window of length L across s, compute each window's rolling hash, and drop the hashes into a set. A repeat hash means a candidate duplicate.

A rolling hash lets each window's hash be computed from the previous one in O(1): drop the leading character and append the trailing one. So one length check is O(n) total, not O(n·L).

Walk through it

Step through the animation on "banana". The lo and hi pointers bound the candidate length. We try L = 3 first, find that "ana" repeats, so we search longer (lo = mid + 1). Length 4 has no repeat, so we shrink from the right (hi = mid − 1). The window collapses and we return the best find, "ana".

Pseudocode

lo, hi = 1, len(s) - 1          # candidate lengths
best = ""
while lo <= hi:
    mid = (lo + hi) // 2
    dup = find_dup_of_length(s, mid)   # rolling hash over all length-mid windows
    if dup is not None:
        best = dup                      # length mid works, try longer
        lo = mid + 1
    else:
        hi = mid - 1                    # too long, try shorter
return best

The Python solution

def longest_dup_substring(s):
    lo, hi = 1, len(s) - 1
    best = ""
    while lo <= hi:
        mid = (lo + hi) // 2
        dup = find_dup_of_length(s, mid)
        if dup is not None:
            best = dup
            lo = mid + 1
        else:
            hi = mid - 1
    return best

• lo, hi bound the length we are searching for, from 1 up to len(s) - 1.
• mid is the length we test this iteration.
• find_dup_of_length(s, mid) slides a length-mid window with a rolling hash and returns a repeated substring, or None.
• If a duplicate exists, we record it and go longer (lo = mid + 1) — longer answers are still possible.
• If not, we go shorter (hi = mid - 1).
• When lo > hi the search ends and best holds the longest duplicate found.

Complexity

We do O(log n) binary-search steps, and each step scans the string once with a rolling hash in O(n) — giving O(n log n). The hash set holds up to O(n) window hashes, so space is O(n).

When this pattern shows up

Practice