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:

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[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;
    }
};