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.

Constraints:

• $$$1 \le word.length \le 10^{5}$$$
• $$$word$$$ consists of lowercase English letters from '$$$a$$$' to '$$$j$$$'.

• For all $$$i$$$ in the range $$$0 \le i \le 2^{10} - 1$$$ we create a map of vectors where map[set_bits(i)].push_back(i);
• Similar to the original question, we will store the $$$XOR$$$ prefix of the string as we traverse. Let's call this $$$sum$$$. Let $$$csum$$$ be the number of set bits in $$$sum$$$.
• We will also store the frequency of the $$$XOR$$$ prefixes we encountered so far as $$$freq[sum]$$$

• For exactly $$$p$$$ letters appearing odd number of times, we need to check with which integer values when $$$XOR'd$$$ with current $$$sum$$$ yields $$$p$$$ number of set bits.

• The integer values must have set bits in the range $$$[csum - p, csum + p]$$$ to yield exactly $$$p$$$ bits. We can get all of the integers using $$$map[i]$$$ where $$$csum - p \le i \le csum + p$$$. Note that all integers within this range of set bits would not yield the required amount bits.
• Update the count if the number of set bits of $$$sum$$$ $$$^$$$ $$$map[i][j] = p$$$
• For every $$$sum$$$ obtained at every index, we iterate $$$p$$$ from $$$0$$$ to $$$k$$$.

class Solution {
    using i64 = long long;
    
private:
    int sum, k;
    i64 cnt;
    std::array<int, (1 << 10)> freq;
    std::unordered_map<int, std::vector<int>> ump;
    
    void precompute() {
        for(int i = (1 << 10) - 1; i >= 0; i--) {
            int j = __builtin_popcount(i);
            ump[j].push_back(i);
        }

        std::fill(freq.begin(), freq.end(), 0);
    }
    
    void compute(int p) {
        int csum = __builtin_popcount(sum);

        for(int i = csum - p; i <= csum + p; i++) {
            for(int j = 0; j < ump[i].size(); j++) {
                int z = sum ^ ump[i][j];

                cnt += (__builtin_popcount(z) == p)? freq[ump[i][j]]: 0;
            }
        }
    }
    
public:
    i64 wonderfulSubstrings(std::string word) {
        precompute();
        
        sum = 0; cnt = 0; k = 1; freq[0] = 1;
        for(const char& ch: word) {
            int bit = ch - 'a';
            sum ^= (1 << bit);
            
            for(int i = 0; i <= k; i++) {
                compute(i);
            }
            ++freq[sum];
        }

        return cnt;  
    }
};

• For calculating the atleast $$$k$$$ variant, we can calculate for atmost $$$k-1$$$ and then subtract it from $$$n*(n+1)/2$$$, $$$n$$$ being the size of the string $$$word$$$.
• For calculating the even variant, we need to keep track of the unset bits, instead of the set bits.