(01状压)超赞字符子串

---

image.png

要求一个连续字串，最多只有一个数重复出现奇数次，其他都是偶数次或者没出现。

剑指有类似题目，通过异或=0使偶数次消去，只剩下唯一的奇数次数。但是这道题只有0-9，所以可以通过异或1<<0 (2^0)到1<<9 (2^9)，得到压缩后的status，只关注0-9是否重复出现。

（1）得到一个当前值异或后的newstatus

（2）通过依次跟1<<0到1<<9异或得到newstatus，查看之前遍历存储的status map里面是否有对应的status，如果有那么更新res，res = max(res,id-map[newstatus])

（3）如果map查不到newstatus，那么就map[newstatus]=id 更新map （我们只需要保留该status离id最远的那个最左端点）

class Solution {
public:
    int longestAwesome(string s) {
        if(s.length()==0){
            return 0;
        }
        unordered_map<int,int>m;
        m[0]=-1;
        int odd=0;
        int res=1;
        for(int i=0;i<s.length();i++){
            odd^=(1<<(s[i]-'0'));
            // double
            if(m.count(odd)==0){
                m[odd]=i;
            }
            res=max(res,i-m[odd]);
            // odd
            for(int j=0;j<10;j++){
                if(m.count(odd^(1<<j))>0){
                    res=max(res,i-m[odd^(1<<j)]);
                }
            }           
        }
        return res;
    }
};