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


  • 3
    C

    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);
                addToRight(signature, s[i]);
                if (i >= 9) {
                    int count = occurred[signature]++;
                    if (count == 1) result.push_back(s.substr(i-9, 10));
                }
            }
            
            return result;
        }
        
        //addition phase
        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;
        }
    

Log in to reply
 

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