# Repeated DNA Sequence

Hash TableBitTwo Pointers

## # Solution

All the following 3 solutions have the same complexities:

Complexity

time: $O(n-L) = O(n)$ for $L=10$
space: $O(n-L) = O(n)$ for $L=10$

### # Sliding Window & HashSet

Move a sliding window of length L == 10 along the string of length n. In the sliding window, if the seqence is not seen yet, add to seen; otherwise, add to output. At the end of for loop, return output.

def findRepeatedDnaSequences(self, s: str) -> List[str]:
L, n = 10, len(s)
seen, output = set(), set()

for i in range(n-L+1):
seq = s[i:i+L]
if seq not in seen:
else:
return output

1
2
3
4
5
6
7
8
9
10
11

### # RK

def findRepeatedDnaSequences(self, s: str) -> List[str]:
L, n = 10, len(s)
# edge case
if n < L:
return []
seen, res = set(), set()
dct = {'A': 0, 'C': 1, 'G': 2, 'T': 3}
hash_s = 0
s_to_int = lambda i: dct[s[i]]
base = 4
mod = 10**9 + 7
power = pow(base, L, mod)

# compute hash of s[0:L] and add to seen
for i in range(L):
hash_s = hash_s*base + s_to_int(i)

for i in range(1, n-L+1):
# compute current hash by multiplying base, subtracting prev*power and adding next
hash_s = hash_s*base - s_to_int(i-1)*power + s_to_int(i+L-1)
if hash_s in seen:
else:
return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

### # Bit Manipulation

Similar to RK, we encode the strings in terms of bits, i.e., A as 00, C as 01, G as 10, and T as 11. We then use bitmask to store encoding of current chars in sliding window into seen if not seen before, and add to output if seen.

def findRepeatedDnaSequences(self, s: str) -> List[str]:
L, n = 10, len(s)
if n <= L:
return []

# convert string to the array of 2-bits integers:
# 00_2, 01_2, 10_2 or 11_2
to_int = {'A': 0, 'C': 1, 'G': 2, 'T': 3}
nums = [to_int.get(s[i]) for i in range(n)]

seen, output = set(), set()
# iterate over all sequences of length L
for start in range(n - L + 1):
# compute bitmask of the sequence in O(1) time
if start != 0:
# left shift to free the last 2 bit
# add a new 2-bits number in the last two bits
bitmask |= nums[start + L - 1]
# unset first two bits: 2L-bit and (2L + 1)-bit
bitmask &= ~(3 << 2 * L)
# compute bitmask of the first sequence in O(L) time
else:
for i in range(L):
return output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 4, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://franklinqin0.me/algo/repeated-dna-sequences.html", "fetch_time": 1726439921000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2024-38/segments/1725700651668.26/warc/CC-MAIN-20240915220324-20240916010324-00670.warc.gz", "warc_record_offset": 261936596, "warc_record_length": 12125, "token_count": 859, "char_count": 2340, "score": 3.5625, "int_score": 4, "crawl": "CC-MAIN-2024-38", "snapshot_type": "latest", "language": "en", "language_score": 0.6331143379211426, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00036-of-00064.parquet"}