# 1915. Number of Wonderful Substrings
###### tags: `Leetcode` `Medium` `Prefix Sum` `HashMap` `Bit Manipulation`
Link: https://leetcode.com/problems/number-of-wonderful-substrings/
## 思路 $O(10N)$ $O(1024)$
因为需要比较之前的每个字母出现的次数是奇数还是偶数 以及 当下每个字母出现的次数是奇数还是偶数 如果一个一个字母记太占空间 所以需要用到bit manipulation
mask是十位数字 每一位各代表一个字母之前出现的次数是奇数还是偶数 1代表奇数 0代表偶数
先从最简单的情况考虑
如果要求subarray里面出现的字母全都是偶数次 那么只需要当下的mask之前出现了多少次 加在res里面就可以
但现在允许有at most one出现奇数次 那么就把当下mask的每一位都flip一遍 然后在答案里加上 之前flip之后的mask出现的次数
## Code

class Solution {
    public long wonderfulSubstrings(String word) {
        long[] cnt = new long[1024];
        long res = 0;
        int mask = 0;
        cnt[mask] = 1;
        for(int i=0; i<word.length(); i++){
            char c = word.charAt(i);
            mask ^= 1<<(c-'a');
            res += cnt[mask];
            for(int j=0; j<10; j++){
                res += cnt[mask ^ (1<<j)];
            }
            cnt[mask]++;
        }
        return res;
    }
}