# Prefix sum and bit manipulation

In last week’s Leetcode weekly contest (June 26, 2021), there is an interesting problem that can be solved by using prefix sum and bit manipulation.

## 1915. Number of Wonderful Substrings

1. all characters have an even number of occurrences.
2. Only one character has an odd number occurrence: try from a to j.

Then the problem can be solved.

A toy example

`/*             0,        a    1        aa   0        aaa  1        */`

From the prefix sum of the above toy example, we can see when the current prefix sum of a is equal to the historical value, then there is an even number of a between those two positions. For example, the initial prefix sum is 0 and when we have “aa” the prefix sum is also 0.

Code

`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 = 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;    }};`

Data Scientist/MLE/SWE @takemobi

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi