Longest Repeated Substring in Java: Binary Search and Rolling Hash

The longest repeated substring problem asks for the longest contiguous sequence of characters that appears at least twice within one string. Occurrences may overlap. For example, banana contains ana twice, beginning at positions 1 and 3 (zero-based). This guide explains an efficient Java approach using binary search and Rabin–Karp rolling hashes, with an important safeguard: verify actual character matches instead of trusting hashes alone.

Problem statement and examples

Given a string s, return any substring of maximum length that appears at least twice. If no nonempty substring repeats, return an empty string. If multiple answers tie for maximum length, any of them is valid. Overlapping occurrences count.

Why binary search works

If a duplicated substring of length L exists, then at least one duplicated substring of every shorter positive length exists as well: for example, take the first L−1 characters of both occurrences. This monotonic property lets us binary-search the maximum possible length from 1 through n−1.

1. Choose a candidate length L from the current search interval.
2. Scan all substrings of length L and check whether any substring occurs twice.
3. If a duplicate exists, save its start index and search for a longer length.
4. Otherwise search shorter lengths. Return the best substring found, or "" if none exists.

How Rabin–Karp rolling hashes find a duplicate

Computing a substring hash from scratch for every starting position would waste time. A rolling hash updates the previous window’s hash by removing the outgoing character, multiplying by a base, and adding the incoming character. This allows the next window hash to be computed in constant arithmetic time.

1. Hash the first window of length L.
2. Store the hash together with its start index.
3. Slide the window one character to the right, update its hash, and look for earlier windows with the same hash.
4. Crucially, compare the actual characters before accepting a duplicate, because different substrings can have identical hashes (a hash collision).

The implementation below computes two modular hashes per substring to reduce accidental collisions. It then calls Java’s String.regionMatches to verify any matching hash candidates before reporting a duplicate. As a result, hash collisions cannot cause an incorrect answer, although unusually many collisions can slow the algorithm.

Correct Java solution: binary search with verified rolling hashes

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    private static final long BASE = 257L;
    private static final long MOD1 = 1_000_000_007L;
    private static final long MOD2 = 1_000_000_009L;

    public String longestDupSubstring(String s) {
        int n = s.length();
        if (n < 2) return "";

        int lo = 1, hi = n - 1;
        int bestStart = -1, bestLength = 0;

        while (lo <= hi) {
            int length = lo + (hi - lo) / 2;
            int start = findDuplicate(s, length);

            if (start != -1) {
                bestStart = start;
                bestLength = length;
                lo = length + 1;
            } else {
                hi = length - 1;
            }
        }
        return bestStart == -1
                ? "" : s.substring(bestStart, bestStart + bestLength);
    }

    private int findDuplicate(String s, int length) {
        int n = s.length();
        long hash1 = 0, hash2 = 0;
        long highestPower1 = 1, highestPower2 = 1;

        for (int i = 0; i < length; i++) {
            hash1 = (hash1 * BASE + s.charAt(i)) % MOD1;
            hash2 = (hash2 * BASE + s.charAt(i)) % MOD2;
            if (i < length - 1) {
                highestPower1 = highestPower1 * BASE % MOD1;
                highestPower2 = highestPower2 * BASE % MOD2;
            }
        }

        Map<Long, List<Integer>> seen = new HashMap<>();
        seen.computeIfAbsent(hashKey(hash1, hash2),
                k -> new ArrayList<>()).add(0);

        for (int start = 1; start <= n - length; start++) {
            int outgoing = s.charAt(start - 1);
            int incoming = s.charAt(start + length - 1);

            hash1 = ((hash1 - outgoing * highestPower1 % MOD1
                     + MOD1) % MOD1 * BASE + incoming) % MOD1;
            hash2 = ((hash2 - outgoing * highestPower2 % MOD2
                     + MOD2) % MOD2 * BASE + incoming) % MOD2;

            long key = hashKey(hash1, hash2);
            List<Integer> candidates = seen.get(key);

            if (candidates != null) {
                for (int earlier : candidates) {
                    // Hashes can collide: compare the actual characters.
                    if (s.regionMatches(earlier, s, start, length))
                        return start;
                }
            } else {
                candidates = new ArrayList<>();
                seen.put(key, candidates);
            }
            candidates.add(start);
        }
        return -1;
    }

    private long hashKey(long h1, long h2) {
        return (h1 << 32) | h2;
    }
}

Java implementation walkthrough

The outer longestDupSubstring method uses binary search over candidate lengths. The findDuplicate helper scans windows of one length, recording hash pairs and starting positions. A match is returned only after regionMatches confirms the text. The code handles empty and single-character inputs with an early return and places the upper search bound at n - 1, since a full-length string cannot occur twice inside itself.

The implementation indexes Java String values using UTF-16 code units. That is appropriate for common interview inputs such as lowercase English letters, but Unicode grapheme clusters and emoji may span multiple code units; character-boundary-aware processing would require a different representation.

Time and space complexity

• Binary-search iterations: O(log n) candidate lengths.
• Rolling-hash scan: typically O(n) hash updates and hash-map operations for one length.
• Expected overall time: approximately O(n log n) under ordinary hashing behavior, plus the work of verifying candidate matches. This is an expected-case characterization, not an unconditional worst-case bound.
• Worst case: hash collisions and repeated substring verification can require more time. The exact comparison step guarantees correctness even when hashes collide.
• Auxiliary space: O(n) for the hash map and recorded candidate positions for one scan.

Common mistakes and pitfalls

• Assuming equal hashes imply equal strings: a hash collision can lead to the wrong answer unless the characters are checked.
• Using an incorrect window-bound: there are exactly n - L + 1 windows of length L. The loop must include the final valid window.
• Forgetting overlapping matches: do not exclude windows simply because their positions overlap. “ana” in “banana” is a valid answer.
• Searching length n: a nonempty length-n substring can occur only once in a string of length n.
• Ignoring small input edge cases: return an empty string when the input has fewer than two characters.

Validation examples

The Java implementation shown above was compiled and checked against a straightforward brute-force reference on 5,000 randomized short strings, in addition to empty, single-character, repeated-character, mixed-case, and punctuation examples. Those tests confirm the expected answer lengths on the tested cases; they do not prove all possible performance bounds.

When to use other algorithms

For very long strings or workloads requiring stronger worst-case analysis, suffix arrays with longest-common-prefix (LCP) computation and suffix automata are other common techniques. Rolling hashes are accessible for interviews, provided you state the collision trade-off and verify matches for correctness.

For another algorithm practice exercise, see our two-pointer solution to Reverse String (LeetCode 344).

C P Gupta

C P Gupta is a YouTuber and Blogger. He is expert in Microsoft Word, Excel and PowerPoint. His YouTube channel @pickupbrain is very popular and has crossed 9.9 Million Views.