Description

Submission

class Solution {
public:
    long long wonderfulSubstrings(string word) {
        vector<int> count(1<<10);   // a-j
        count[0] = 1;

        int state = 0;
        long long ret = 0;
        for(auto& ch: word) {
            int idx = ch - 'a';
            state = state ^ (1 << idx); // flip the idx-th bit

            // current letter with previous letters
            // zero letter odd number of times
            ret += count[state];

            // 1 letter odd number of times
            for(int i = 0; i < 10; ++i) {
                int newState = state ^ (1 << i);
                ret += count[newState];
            }

            ++count[state];
        }

        return ret;
    }
};


// a through j: 0 - 9
// prefix
// for the i-th and j-th
// for zero letter odd number
// XXXXXXi[XXXXXj]
// count['a'][j]%2
// count['b'][j]%2
// .
// count['j'][j]%2

// should be congruent with

// count['a'][i]%2
// count['b'][i]%2
// .
// count['j'][i]%2

// extract the last bit from each of these numbers
// 1 -> 0, 0 -> 1, xor