Leetcode 187: 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"]. 

题目大意： 在给定字符串里面找长度为10的子字符串，并且该子字符串在字符串里出现1次以上。

这个题目的key word是 bit manipulation， hash table 

用字符编码来解决。  

刚看到这个题目觉得是不是跟长度为10的sliding window差不多，一个子字符串地去match，后来发现

这个题目是substring,是严格相等的而不只是字符出现次数相同，这样的话就觉得好像跟在一个int array

里面找occurance > 1的int差不多，是不是建立一个hashmap记录每个长度为10的子字符串次数就可以？ 

但是这样做的话hashmap的key是string, 占用的空间太大，而且每次都需要做substr的操作，有没有方法

可以减少空间并且不用每次都取substr呢?

后来看论坛发现其实可以对每10个字符的substring 进行先hash成int再存到map里面，那么如何hash呢？

由于只会出现4个字符： A, G, C , T,并且子字符串都是这4个字符的组成， 如果对A,G,C,T分别编码，

A： 00， C：01， G： 10， T： 11

个子字符串是这4个字符的编码组成， 那么相同的子字符串的编码也是相同的。

比如AAAAACCCCC： 00000000000101010101

因为10个字符一共是20个bit,所以每次只要取32位的后20位就可以，用掩码： 0xFFFFF来取。 

 每次移动一个字符取下一个10个字符的时候，移出的那个字符会自动过滤，保证了每次用掩码取的都是

最新的20个bit，即最近的10个字符。

updated：

如果从A,G,C,T的ascII码来看的话 

A: 1000001

C: 1000011

G: 1000111

T: 1010100

最后三位是不同的，我们可以直接取最后三位来代替字符映射的map，这样的话就是用3个bit来代替一个字符，10个字符-》30个bit，正好可以用一个int型的数来表示，每次我们取最后30位，用掩码： 0x 3FFFFFFF .

time complexity :  o(N) space complexity: o(N)

 class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> rst;
        //sanity check
        if (s.size() == 0) return rst;
        map<int, int> hashmap;
        int sum = 0;
        for (int i = 0; i < s.size(); i++) {
            sum = ((sum << 3) + (s[i] & 7)) & 0x3FFFFFFF;
            if (i < 9) continue;
            if (hashmap[sum] == 1) {
                rst.push_back(s.substr(i-9, 10));
            }
            hashmap[sum]++;
        }
        return rst;
    }
};