Introduction

Duplicate substring searching asks whether a string contains the same contiguous sequence of characters more than once. Sometimes the goal is to find any repeated substring, and sometimes the goal is to find the longest repeated substring, which is a harder problem and usually changes the algorithm choice.

Start with the Naive Approach

The simplest idea is to enumerate substrings and remember what you have seen:

1def find_duplicate_substrings(s):
2    duplicates = set()
3    seen = set()
4
5    for start in range(len(s)):
6        for end in range(start + 1, len(s) + 1):
7            sub = s[start:end]
8            if sub in seen:
9                duplicates.add(sub)
10            else:
11                seen.add(sub)
12
13    return duplicates
14
15
16print(sorted(find_duplicate_substrings("banana")))

This is easy to understand, but it is expensive. There are O(n^2) substrings, and creating or comparing them repeatedly can push the practical cost much higher.

Clarify the Exact Question

Before optimizing, decide what you need:

• any duplicate substring
• all duplicate substrings
• the longest duplicate substring
• duplicate substrings of at least a certain length

Those are related problems, but they are not the same. A quick set-based solution may be fine for "does any duplicate exist" on short strings, while "find the longest duplicate substring" usually needs a more specialized approach.

Use Binary Search Plus Rolling Hash for the Longest Case

For large inputs, a common technique is binary search on substring length combined with a rolling hash. The binary search asks: "does a duplicate substring of length k exist?" If yes, try longer; if not, try shorter.

Here is a simplified version:

1def has_duplicate_of_length(s, length):
2    seen = set()
3    for i in range(len(s) - length + 1):
4        sub = s[i:i + length]
5        if sub in seen:
6            return True
7        seen.add(sub)
8    return False
9
10
11def longest_duplicate_length(s):
12    left, right = 1, len(s) - 1
13    answer = 0
14
15    while left <= right:
16        mid = (left + right) // 2
17        if has_duplicate_of_length(s, mid):
18            answer = mid
19            left = mid + 1
20        else:
21            right = mid - 1
22
23    return answer
24
25
26print(longest_duplicate_length("banana"))

This version still slices strings, so it is not the most optimized possible implementation, but it shows the core strategy clearly. In production, rolling hashes or suffix-array-style approaches reduce repeated substring comparisons.

Know the Tradeoff Between Simplicity and Scale

For interview problems or small inputs, the simpler solution is often preferable because it is easier to reason about and verify. For very large strings, repeated slicing becomes expensive, and data structures such as suffix arrays, suffix automata, or Rabin-Karp style rolling hashes become more attractive.

That is why the right answer depends heavily on the expected input size and on whether you need exact matches, counts, or only one representative substring.

Common Pitfalls

The biggest mistake is not defining the problem precisely. "Find duplicate substrings" can mean several different things, and each version suggests a different implementation.

Another issue is underestimating the number of substrings. Even moderate string lengths can produce a large amount of work for naive algorithms.

People also forget about overlapping duplicates. In "banana", the substring "ana" appears more than once with overlap, and many formulations of the problem count that as a valid duplicate.

Finally, if you switch to hashing for speed, remember that careless hashing can introduce collisions. A robust solution either uses a collision-resistant strategy or verifies candidate matches explicitly.

Summary

• Duplicate substring searching can mean "any", "all", or "longest" repeated substrings.
• A naive set-based approach is easy to write but grows expensive quickly.
• Binary search plus substring existence checks is a common strategy for longest-duplicate problems.
• Large inputs may require rolling hashes or suffix-based data structures.
• Define whether overlapping duplicates count before choosing an algorithm.