# Leetcode: Repeated DNA Sequences

Repeated DNA Sequences

Similar Problems:

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: “ACGAATTCCG”. When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

```Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].
```

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```## Blog link: https://code.dennyzhang.com/repeated-dna-sequences
## Basic Ideas: sliding window + hashmap
##
## Complexity: Time O(n), Space O(n)
class Solution(object):
def findRepeatedDnaSequences(self, s):
"""
:type s: str
:rtype: List[str]
"""
length = len(s)
if length <= 10: return []
import collections
d = collections.defaultdict(lambda:0)
curStr = s[0:10]
d[curStr] += 1
res = []
for i in range(10, length):
curStr = curStr[1:] + s[i]
if d[curStr] == 1: res.append(curStr)
d[curStr] += 1
return res
```

Share It, If You Like It.