# Can anyone tell me how get AC result below 50ms using C++

• I tested several AC codes posted by others, finding that using bit
manipulation (C++), we can only get AC result in more than 100ms, can
anyone post solutions below 50ms?

• I'm interested in this too - of course could cheat and do lookup table (only 30 cases, so shouldn't take long), but I assume there is a legit solutions.

Here is my solution so far - 108ms. I hoped bitwise operations would be able to get time down, but didn't seem to do too much better

``````vector<string> findRepeatedDnaSequences(string s) {
int mask = ~0, i, id=0;
int n = s.length();
vector<string> out;
unordered_set<int> seen, included;
i=-1;
while(++i<n){
id<<=2;
if (s[i]=='G') id ^=1;
if (s[i]=='C') id ^=2;
if (s[i]=='T') id ^=3;
if (i<9) continue;
if (seen.find(id)==seen.end()) {seen.insert(id); continue;}
if (included.find(id)!=included.end()) continue;
included.insert(id);
out.push_back(s.substr(i-9, 10));
}
return out;
}``````

• You need to use array instead of STL to get the best performance.

The following code runs in 18ms, it's slightly modified from my other question.

``````vector<string> findRepeatedDnaSequences(string &s) {
vector<string> r;
int t = 0, i = 0, ss = s.size(), m[1 << 20] = {0};
while (i < 9)
t = t << 2 | s[i++] >> 1 & 3;
while (i < ss)
if (m[t = t << 2 & 0xFFFFF | s[i++] >> 1 & 3]++ == 1)
r.emplace_back(s, i - 10, 10);
return r;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.