Repeated DNA Sequences (LeetCode 187)

The problem

A DNA string s uses only the letters A, C, G and T. Return every substring of length 10 that appears more than once in s. Each repeated sequence should be listed once; any order is fine (this solution returns them sorted).

Input:  s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC", "CCCCCAAAAA"]

"AAAAACCCCC" starts at index 0 and again at 10. "CCCCCAAAAA" starts at 5 and again at 16.

How to think about it

Start with brute force. For every window, compare it against every other window. With n − 9 windows that’s O(n²) comparisons of 10 characters each, too slow for n = 10⁵.

The key insight: remember what you’ve seen. Slide a window of length 10 along s. Keep a set seen of every window so far. If the current window is already in seen, it’s a repeat, so add it to a second set res. Using a set for res means a sequence that appears three times is still reported once.

Why this is the Rabin-Karp idea. Putting a string in a hash set means fingerprinting it with a hash. Rabin-Karp’s improvement is to compute each window’s fingerprint in O(1) from the previous one (a rolling hash), instead of hashing all 10 characters again. With the window fixed at 10 the slicing version is already linear; the rolling hash matters when the window is long or variable, as in Longest Duplicate Substring.

Which pattern is this? Fixed-size window plus hashing. The tell is “find substrings of a given length that repeat”.

Approach

1. Create two empty sets: seen and res.
2. For every start i from 0 to len(s) - 10, take sub = s[i:i + 10].
3. If sub is in seen, add it to res.
4. Add sub to seen.
5. Return sorted(res).

Solution

def findRepeatedDnaSequences(s):
    seen = set(); res = set()
    for i in range(len(s) - 9):          # every length-10 window
        sub = s[i:i + 10]
        if sub in seen:
            res.add(sub)                 # second (or later) sighting
        seen.add(sub)
    return sorted(res)
# findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT") -> ["AAAAACCCCC","CCCCCAAAAA"]

Dry run

The example has 32 characters, so 23 windows. Most are seen once; these are the moments that matter:

After all 23 windows, seen holds 21 distinct sequences and res holds the two repeats.

Complexity

• Time: O(n · L) with L = 10, which is O(n). Each window is sliced and hashed in O(10). A rolling hash would make each step O(1).
• Space: O(n · L). Up to n stored windows of 10 characters each. Encoding each window as a 20-bit integer (2 bits per letter) shrinks this.

Edge cases and pitfalls

• len(s) < 10: range is empty and the answer is [].
• Overlapping repeats count. "AAAAAAAAAAA" (11 A’s) has two overlapping windows of ten A’s, so "AAAAAAAAAA" is reported.
• Reporting duplicates. If res were a list, a sequence seen three times would be added twice.
• Off-by-one in the range. The last window starts at len(s) - 10, so the loop is range(len(s) - 9).
• Counting with a dict and filtering count > 1 is an equally good answer.

Related problems

• Longest Duplicate Substring (LeetCode 1044): the same seen-set idea with a real rolling hash and an unknown length.
• Find All Anagrams in a String (LeetCode 438): a fixed-size window fingerprinted by letter counts.
• Group Anagrams (LeetCode 49): grouping strings by a hashable key.