Repeated DNA Sequences

How it works

DNA sequences use only four characters (A, C, G, T), each of which can be encoded with just 2 bits. A 10-character sequence therefore fits in 20 bits, well within a single integer. By treating each sequence as a mask, we avoid storing strings entirely and get fast integer operations for comparisons and hashing.

Steps

1. If the string length is less than 10, return an empty list.
2. Map each nucleotide to a 2-bit value: A=0, C=1, G=2, T=3 in map mp.
3. Initialize a mask to zero and a hash map cnt for counting.
4. For each character at index i, shift the mask left by 2 bits and OR with the character's value.
5. Mask the result with 0xFFFFF to keep only the rightmost 20 bits (10 characters).
6. Once the window reaches size 10, increment the count for this mask.
7. When a mask appears the second time, add the corresponding substring to res.
8. Return the res list.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Adding Duplicates to the Result

When a sequence appears three or more times, it should only be added to the result once. Using a single set without tracking whether the sequence was already added to the result causes duplicates in the output.

Off-by-One Errors in Window Boundaries

The sliding window must extract exactly 10 characters. Common mistakes include using s[l:l+9] instead of s[l:l+10], or iterating with range(len(s) - 10) instead of range(len(s) - 9), which skips valid windows or causes index errors.

Incorrect Bit Mask Width in the Optimized Approach

When using bit manipulation, each nucleotide requires 2 bits, so a 10-character sequence needs 20 bits. Using the wrong mask value (such as 0xFFFF for 16 bits instead of 0xFFFFF for 20 bits) causes hash collisions between different sequences.

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> list[str]:
        if len(s) < 10:
            return []

        mp = {'A': 0, 'C': 1, 'G': 2, 'T': 3}
        seen, res = set(), set()
        mask = 0
        for i in range(len(s)):
            mask = ((mask << 2) | mp[s[i]]) & 0xFFFFF
            if i >= 9:
                if mask in seen:
                    res.add(s[i - 9: i + 1])
                else:
                    seen.add(mask)

        return list(res)

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        if (s.length() < 10) return {};

        unordered_map<char, int> mp = {{'A', 0}, {'C', 1},
                                       {'G', 2}, {'T', 3}};
        unordered_map<int, int> cnt;
        vector<string> res;
        int mask = 0;

        for (int i = 0; i < s.size(); i++) {
            mask = ((mask << 2) | mp[s[i]]) & 0xFFFFF;

            if (i >= 9) {
                cnt[mask]++;
                if (cnt[mask] == 2) {
                    res.push_back(s.substr(i - 9, 10));
                }
            }
        }

        return res;
    }
};