1915. Number of Wonderful Substrings

A wonderful string is a string where at most one letter appears an odd number of times.

• For example, “ccjjc” and “abab” are wonderful, but “ab” is not.

Given a string word that consists of the first ten lowercase English letters (‘a’ through ‘j’), return the number of wonderful non-empty substrings in word. If the same substring appears multiple times in word, then count each occurrence separately.

A substring is a contiguous sequence of characters in a string.

class Solution {
public:
    long long wonderfulSubstrings(string word) {
        long prefix[1024]{1}, res(0), mask(0);
        for(auto& c: word) {
            mask ^= 1<<(c-'a');
            res += prefix[mask]++;
            for(int i = 0; i < 10; i++)
                res += prefix[mask ^ (1<<i)];
        }
        return res;
    }
};