Repeated DNA Sequences
Problem
A DNA strand is a string over the letters A, C, G and T. Return every length-10 substring that occurs more than once in the strand, sorted, with each such substring listed only once no matter how often it repeats.
Examples
Input: dna = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC", "CCCCCAAAAA"]
Why: both windows appear twice inside the strandInput: dna = "AAAAAAAAAAAA"
Output: ["AAAAAAAAAA"]
Why: the same window slides along and repeatsInput: dna = "ACGT"
Output: []
Why: edge case, the strand is shorter than one windowHints
0 / 3
Slicing out every window and storing the strings works but copies ten characters per position. Think about what changes when the window slides one step.
Only four letters exist, so each one fits in two bits and a ten-letter window fits in twenty — small enough to be a single integer key.
Keep the window as a number. Sliding right means shifting it two bits left, adding the new letter's code, and masking off the bits that fell out of the window. Record each window number in a set and collect the ones seen a second time.
Solution
Two bits per letter turn a ten-letter window into a twenty-bit integer, so the whole window is one machine word rather than a string. Sliding is then three constant-time operations — shift in the arriving letter, mask out the departing one — instead of a fresh ten-character slice. A set of seen window values catches repeats, and a second set keeps the answer free of duplicates. Time is O(n) and space is O(n) in the number of distinct windows.
def repeated(dna, k=10):
seen, twice = set(), set()
code = {"A": 0, "C": 1, "G": 2, "T": 3}
h, mask = 0, (1 << (2 * k)) - 1
for i, ch in enumerate(dna):
h = ((h << 2) | code[ch]) & mask # shift in, mask out
if i >= k - 1:
if h in seen:
twice.add(dna[i - k + 1:i + 1]) # slice only on a hit
seen.add(h)
return sorted(twice)
print(repeated("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT")) # -> ['AAAAACCCCC', 'CCCCCAAAAA']
print(repeated("AAAAAAAAAAAA")) # -> ['AAAAAAAAAA']
print(repeated("ACGT")) # -> []Stuck on the idea rather than the code? Rabin-Karp Rolling Hash covers it.