# Well-organized sliding window C++ solution, beating 94%

• This is a typical sliding window problem. Since the window size is 10 and possible char is ACGT, we can encode the string covered by the window using 20-bit integer.

The key thing here is how to update the window. There are 2 possible cases for window, one is 1) window size < 10 2) window size == 10

During the initial setup phase the window size is less than 10, so each time we only add to window. Then when window size reaches 10, we need to pop out and push back.

So we can abstract it into two actions 1) eviction, 2) addition

If window size < 10, we only do addition
If window size == 10, we do eviction first, then addition.

This is also a very recommended style for all sliding window problems. Breaking up the logical of updating a window into eviction phase and addition phase can simplify and modulize the overall solution

``````    vector<string> findRepeatedDnaSequences(string s) {
if (s.size() < 10) return {};
unsigned int signature = 0;
unordered_map<unsigned int, int> occurred;

vector<string> result;
for (int i=0; i<s.size(); i++) {
if (i > 9) removeLeft(signature);
if (i >= 9) {
int count = occurred[signature]++;
if (count == 1) result.push_back(s.substr(i-9, 10));
}
}

return result;
}

void addToRight(unsigned int& signature, char c) {
signature <<= 2;
if (c == 'A') {
signature |= 0x0;
} else if (c == 'C') {
signature |= 0x1;
} else if (c == 'G') {
signature |= 0x2;
} else {
signature |= 0x3;
}
}

//eviction phase
void removeLeft(unsigned int& signature) {
signature &= (1 << 18) - 1;
}
``````

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