# 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

For each character, we check the following cases:

- all characters have an even number of occurrences.
- 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[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;

}

};