(状压dp)1915. 最美子字符串的数目

1915. 最美子字符串的数目

class Solution {
public:
    long long wonderfulSubstrings(string word) {
        map<int, int> mp = {{0, 1}};
        long long res = 0;
        int mask = 0;
        for (auto c:word) {
            mask ^= 1 << (c - 'a');
            res += mp[mask];
            for (int i = 0; i < 10; i++) {
                int tmask = mask ^(1 << i);
                res+=mp[tmask];
            }
            mp[mask]++;
        }
        return res;
    }
};