Generated by Codex with GPT-5

Quick facts

• Difficulty: HARD
• Problem: Longest Duplicate Substring
• Topics: String, Binary Search, Sliding Window, Rolling Hash, Suffix Array, Hash Function

Problem gist

Given a string s, the task is to return any longest substring that appears at least twice in s. The two occurrences may overlap. For example, in banana, the answer is ana, because ana appears starting at index 1 and again at index 3.

The brute-force idea is to generate every substring and remember which ones have appeared before. That is easy to imagine, but too slow: there are O(n^2) substrings, and copying or comparing them can add another factor.

The useful observation is that the answer length has a monotonic shape:

• If a duplicate substring of length L exists, then a duplicate substring of every smaller length also exists by taking a prefix of those same two occurrences.
• If no duplicate substring of length L exists, then no duplicate substring of any larger length can exist.

That means the length can be found with binary search. The remaining question is how to check one fixed length quickly.

Core idea

For a chosen length L, slide a window of size L across the string. If two windows have exactly the same substring, then a duplicate of length L exists.

Comparing each new window against all previous windows would still be too expensive. Rolling hash fixes that. It gives each window a numeric fingerprint and updates that fingerprint in O(1) when the window moves one character to the right.

The check for a fixed length works like this:

1. Compute the rolling hash for the first window.
2. Store the hash and its start index.
3. Slide one character at a time.
4. If the new hash has not been seen, store it.
5. If the new hash has been seen, verify the actual substring against the previous starts with that same hash.
6. If any verified match is equal, return that start index.

The verification step is important in real code. Hash collisions are rare with two large moduli, but rare is not the same as impossible. Checking the actual substring after a hash match keeps the algorithm logically correct.

The full algorithm is:

1. Binary search the candidate duplicate length from 1 to len(s) - 1.
2. Use rolling hash to decide whether that length exists.
3. When a length works, remember one duplicate and try a longer length.
4. When a length fails, try shorter lengths.
5. Return the best duplicate found.

This runs in O(n log n) expected time with O(n) extra space. The substring verification cost is normally tiny because double-hash collisions are uncommon and true duplicates end the check immediately. A suffix array solution avoids hashing entirely and is a strong deterministic alternative, but rolling hash plus binary search is usually the most direct interview solution.

Python solution

from collections import defaultdict
from typing import DefaultDict, List, Optional, Tuple


class Solution:
    _BASE = 911_382_323
    _MOD_1 = 1_000_000_007
    _MOD_2 = 1_000_000_009

    def longestDupSubstring(self, s: str) -> str:
        if len(s) < 2:
            return ""

        values = [ord(char) + 1 for char in s]
        best_start = 0
        best_length = 0

        left = 1
        right = len(s) - 1

        while left <= right:
            candidate_length = (left + right) // 2
            duplicate_start = self._find_duplicate_start(
                s,
                values,
                candidate_length,
            )

            if duplicate_start is None:
                right = candidate_length - 1
            else:
                best_start = duplicate_start
                best_length = candidate_length
                left = candidate_length + 1

        return s[best_start : best_start + best_length]

    def _find_duplicate_start(
        self,
        text: str,
        values: List[int],
        length: int,
    ) -> Optional[int]:
        """Return one duplicate start for this length, or None if none exists."""
        if length == 0:
            return 0
        if length >= len(text):
            return None

        hash_1, hash_2 = self._initial_hash(values, length)
        power_1 = pow(self._BASE, length - 1, self._MOD_1)
        power_2 = pow(self._BASE, length - 1, self._MOD_2)

        starts_by_hash: DefaultDict[Tuple[int, int], List[int]] = defaultdict(list)
        starts_by_hash[(hash_1, hash_2)].append(0)

        for start in range(1, len(text) - length + 1):
            left_value = values[start - 1]
            right_value = values[start + length - 1]

            hash_1 = self._roll_hash(
                hash_1,
                left_value,
                right_value,
                power_1,
                self._MOD_1,
            )
            hash_2 = self._roll_hash(
                hash_2,
                left_value,
                right_value,
                power_2,
                self._MOD_2,
            )

            key = (hash_1, hash_2)
            for previous_start in starts_by_hash[key]:
                previous = text[previous_start : previous_start + length]
                current = text[start : start + length]
                if previous == current:
                    return start

            starts_by_hash[key].append(start)

        return None

    def _initial_hash(self, values: List[int], length: int) -> Tuple[int, int]:
        hash_1 = 0
        hash_2 = 0

        for index in range(length):
            value = values[index]
            hash_1 = (hash_1 * self._BASE + value) % self._MOD_1
            hash_2 = (hash_2 * self._BASE + value) % self._MOD_2

        return hash_1, hash_2

    def _roll_hash(
        self,
        current_hash: int,
        left_value: int,
        right_value: int,
        left_power: int,
        modulus: int,
    ) -> int:
        without_left = (current_hash - left_value * left_power) % modulus
        return (without_left * self._BASE + right_value) % modulus

Why it works

The binary search is valid because duplicate existence is monotonic by length. A successful duplicate of length L immediately proves that shorter duplicate lengths exist too. A failed check at length L rules out every longer length because any longer duplicate would contain a duplicate prefix of length L.

The rolling-hash scan is valid because it considers every substring of exactly the candidate length. If two equal substrings exist, they produce the same pair of rolling hashes, so the later one will inspect the earlier start under that hash key and verify the actual text. If no verified match appears, then no duplicate of that length exists.

The algorithm always keeps the longest successful length seen so far. Binary search only moves right after a successful check, so the final saved substring has the maximum possible duplicate length.

Complexity

For each candidate length, the rolling scan touches O(n) windows and stores up to O(n) start indices. Binary search tries O(log n) lengths, so the expected runtime is O(n log n) and the extra space is O(n).

The code verifies actual substrings after hash matches. With double hashing, accidental collisions are extremely unlikely; true duplicate matches return immediately. If an interviewer requires a completely deterministic collision-free method, use a suffix array plus an LCP array instead.

Interview follow-ups

How would you solve it without hashing?

Use a suffix array. Sort all suffixes of the string lexicographically, then compare neighboring suffixes. Any duplicated substring must be a common prefix of two suffixes, and the longest duplicate substring is the largest longest-common-prefix value among adjacent suffixes in sorted order.

This works because sorting brings suffixes with shared prefixes next to each other. After that, the LCP array captures exactly how much each neighboring pair shares. A doubling-based suffix array is often O(n log^2 n) or O(n log n) depending on implementation details, and Kasai’s algorithm builds the LCP array in O(n). The tradeoff is more code and more indexing machinery, but the result is deterministic.

Why is binary search legal here?

The key is the monotonic predicate: “there exists a duplicate substring of length L.” If it is true for L, it is true for smaller lengths. If it is false for L, it is false for larger lengths.

That shape is exactly what binary search needs. The algorithm is not guessing the substring itself; it is searching for the largest length that passes a yes-or-no duplicate test.

Do overlapping duplicates count?

Yes. The problem asks whether the same substring occurs at least twice, not whether the occurrences are disjoint. In banana, the two copies of ana overlap, and that is still valid.

The algorithm naturally supports this because it stores start indices and compares substrings directly. It never rejects a candidate just because the ranges intersect.

How would you return all longest duplicate substrings?

First run the same binary search to find the maximum valid length. Then perform one final rolling-hash scan at that exact length and collect every verified substring that appears more than once.

The main tradeoff is output size. The scan is still expected O(n), but storing all answers can take additional space proportional to the number and size of distinct longest duplicates. To avoid repeated large string copies, store start indices during the scan and materialize substrings only when producing the final result.

What if the input alphabet is larger than lowercase English letters?

The algorithm does not depend on lowercase letters. It only needs a stable integer value for each character. Python’s ord(char) is enough for ordinary strings, while byte-oriented production code could hash raw byte values instead.

The complexity stays the same. A larger alphabet may influence hash distribution, but using modular arithmetic with a fixed base and two large prime moduli keeps the rolling-hash mechanics unchanged.