Repeated DNA Sequences — 2-Bit Encoding Rolling Hash with Bitwise AND

Problem Statement#

Given a string s containing only the characters A, C, G, T, return all 10-letter substrings that appear more than once in s. You may return the answer in any order.

Constraints:

• 1 <= s.length <= 10^5
• s[i] is one of 'A', 'C', 'G', 'T'

Examples:

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

Why This Problem Matters#

This problem appears verbatim in Google and Amazon screens. It looks like a hash-set warm-up, but interviewers escalate it to test bit manipulation depth: "Can you do it without storing 10-character strings?" The optimal answer encodes each nucleotide in 2 bits, packing a 10-letter window into a 20-bit integer that updates in O(1) per slide. It's a clean introduction to rolling hashes — the same engine behind Rabin-Karp string matching and bioinformatics k-mer search.

The Core Insight (the bit-trick)#

There are only 4 nucleotides, so each fits in 2 bits:

A -> 00
C -> 01
G -> 10
T -> 11

A 10-letter window = 10 * 2 = 20 bits, fits comfortably in a 32-bit integer. To slide the window one character right:

1. Shift left by 2 to make room: hash = hash << 2.
2. OR in the new character's 2-bit code: hash |= encode(s[i]).
3. Mask off bits above 20 so old characters drop off: hash &= 0xFFFFF (which is (1 << 20) - 1).

Each update is constant time and constant memory. Track seen hashes in a set; the second time you see one, record the substring.

This is materially faster than hashing 10-character strings: integer comparison in a Python set is far cheaper than string hashing, and in C++ / Java the speedup is even more dramatic.

Visual Dry Run (binary representation trace)#

Slide through s = "AAAAAACCCCCC" (length 12). Window size = 10. Mask = 0xFFFFF.

After char 0 'A': hash = 00
After char 1 'A': hash = 0000
After char 2 'A': hash = 000000
...
After char 9 'A': hash = 00000000000000000000  (twenty zero bits) -> first window "AAAAAAAAAA"
  seen = {0x00000}
 
Slide to position 10, new char 'C' (code 01):
  hash = (hash << 2) | 01 = 00000000000000000001
  hash &= 0xFFFFF        = 00000000000000000001  (top bits already zero)
  Window = "AAAAAAAAAC", code 0x00001
  seen = {0x00000, 0x00001}
 
Slide to position 11, new char 'C':
  hash = (0x00001 << 2) | 01 = 0x00005
  Window = "AAAAAAAACC"
  ...

Now consider s = "AAAAAACCCCCAAAAACCCCC" — when the second "CCCCCAAAAA" window arrives, its 20-bit hash exactly matches the first one, and we record it.

The mask step is what evicts the leftmost character: as you shift left, the oldest 2 bits eventually move beyond bit 19, and & 0xFFFFF drops them.

Solution (Optimal)#

Python#

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> list[str]:
        if len(s) < 10:
            return []
 
        encode = {'A': 0, 'C': 1, 'G': 2, 'T': 3}
        MASK = (1 << 20) - 1     # 20 lowest bits set
        seen, repeated = set(), set()
        h = 0
 
        for i, ch in enumerate(s):
            h = ((h << 2) | encode[ch]) & MASK
            if i >= 9:
                if h in seen:
                    repeated.add(s[i - 9 : i + 1])
                else:
                    seen.add(h)
 
        return list(repeated)

JavaScript#

var findRepeatedDnaSequences = function (s) {
  if (s.length < 10) return [];
 
  const encode = { A: 0, C: 1, G: 2, T: 3 };
  const MASK = (1 << 20) - 1;
  const seen = new Set();
  const repeated = new Set();
  let h = 0;
 
  for (let i = 0; i < s.length; i++) {
    h = ((h << 2) | encode[s[i]]) & MASK;
    if (i >= 9) {
      if (seen.has(h)) {
        repeated.add(s.substring(i - 9, i + 1));
      } else {
        seen.add(h);
      }
    }
  }
  return [...repeated];
};

Complexity: Time O(n) — each character processed in O(1). Space O(n) worst case for the hash set.

Common Mistakes#

• Storing strings instead of integers. Works but slower — integer hashing beats string hashing 5-10x in tight loops.
• Forgetting the mask. Without & MASK, old characters never drop off and the hash drifts.
• Wrong mask width. It must be 2 * window_size = 20 bits, i.e. (1 << 20) - 1. Using 10 bits drops half of every character.
• Off-by-one on the window-ready check. The first complete window ends at i = 9 (zero-indexed), not i = 10.
• Returning duplicates when a substring appears 3+ times. Use a set for repeated, not a list.

Interview Tips#

• Start with the naive substring + hash set solution to anchor correctness, then propose the bitmask rolling hash as the optimization. Interviewers love seeing the progression.
• Explicitly call out: "Each character is one of four values, so 2 bits each. The full window fits in 20 bits, well within a 32-bit int."
• Mention that this generalizes to Rabin-Karp for arbitrary alphabets — replace 2-bit packing with a polynomial hash modulo a large prime.
• If asked about collisions: with full 20-bit packing for a 4-letter alphabet there are no collisions — each window has a unique encoding. That's a major point of bit packing over polynomial hashing.

Follow-up Questions#

1. Variable window length k. Replace 20 with 2 * k and update the mask accordingly. For k > 32 switch to two 64-bit halves or polynomial hash.
2. Larger alphabet (e.g. amino acids, 20 letters). 5 bits per letter; for length-10 windows you need 50 bits — fits in a 64-bit integer.
3. Find sequences that appear exactly twice. Switch from a set to a counter dict: include a window if its count after the increment equals 2.
4. Stream version where s arrives one char at a time and you must report repeats online. The same rolling hash works — just emit on first duplicate detection.
5. Memory-constrained version. Use a Bloom filter on the 20-bit hashes to confirm "possibly seen" before paying the substring storage cost.

Key Takeaways#

• A 4-letter alphabet packs cleanly into 2 bits per character — leverage this for any DNA / RNA / nucleotide problem.
• Rolling hashes update in O(1) using shift left, OR new char, AND mask.
• The mask (1 << 20) - 1 is what evicts the leftmost character as you slide.
• 2-bit packing has zero collisions for length-10 DNA windows — much stronger than polynomial hashing.
• This pattern generalizes to Rabin-Karp, k-mer counting in bioinformatics, and substring deduplication in log analysis.
• Always handle the len(s) < 10 edge case at the top.