# LeetCode Repeated DNA Sequences

LeetCode Repeated DNA Sequences

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"].```

```class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
vector<string> ans;
unordered_map<string, int> hash;
for (size_t i = 0; i + 10 <= s.size(); ++i) {
string seq = s.substr(i, 10);
++hash[seq];
if (hash[seq] == 2)ans.push_back(seq);
}
return ans;
}
};
```

```class Solution {
private:
unsigned int encode(const string &s) {
unsigned int code = 0;
for (size_t i = 0; i < s.size(); ++i) {
code <<= 2;
switch (s[i]) {
case 'A':code += 0; break;
case 'T':code += 1; break;
case 'C':code += 2; break;
case 'G':code += 3; break;
}
}
return code;
}
public:
vector<string> findRepeatedDnaSequences(string s) {
vector<string> ans;
unordered_map<unsigned int, int> hash;
for (size_t i = 0; i + 10 <= s.size(); ++i) {
string seq = s.substr(i, 10);
unsigned int code = encode(seq);
++hash;
if (hash == 2)ans.push_back(seq);
}
return ans;
}
};
```