# Prefix sum and bit manipulation

## 1915. Number of Wonderful Substrings

`/*             0,        a    1        aa   0        aaa  1        */`
`typedef long long LL;class Solution {public:    int helper(int curr,  unordered_map<int, int>& cnt, int j){        int prev_matched = curr ^ (1 << j);        return  cnt[prev_matched];       }    long long wonderfulSubstrings(string word) {        const int n = word.size();        vector<int> cusum;        cusum.push_back(0);        for (int i = 0; i < n; ++i)        {            cusum.push_back(cusum.back() ^ (1 << (word[i] - 'a')));        }        LL ret = 0;        /*             0,        a    1        aa   0        aaa  1        */        unordered_map<int, int> cnt;        cnt[0] = 1;        for (int i = 0; i < n; ++i)        {            // even for all            ret += cnt[cusum[i+1]];            // odd for a, b, c, ... j            for (int j = 0; j <= int('j' - 'a'); ++j){                auto thisret = helper(cusum[i + 1], cnt, j);                ret += (LL)thisret;            }              cnt[cusum[i + 1]] += 1;        }        return ret;    }};`

--

--

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.