Count substrings having atmost one letter odd number of times | HARD | OA | MUST DO

https://leetcode.com/problems/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.



Example 1:
Input: word = "aba"
Output: 4
Explanation: The four wonderful substrings are underlined below:
- "aba" -> "a"
- "aba" -> "b"
- "aba" -> "a"
- "aba" -> "aba"

Example 2:
Input: word = "aabb"
Output: 9
Explanation: The nine wonderful substrings are underlined below:
- "aabb" -> "a"
- "aabb" -> "aa"
- "aabb" -> "aab"
- "aabb" -> "aabb"
- "aabb" -> "a"
- "aabb" -> "abb"
- "aabb" -> "b"
- "aabb" -> "bb"
- "aabb" -> "b"

Example 3:
Input: word = "he"
Output: 2
Explanation: The two wonderful substrings are underlined below:
- "he" -> "h"
- "he" -> "e"

Constraints:
1 <= word.length <= 10^9
word consists of lowercase English letters from 'a' to 'j'.

-----------------------------------------------------------------------------------------------------------------------

class Solution {
public:
    long long helper(string &word, char x){
        int desiredMask=(1 << (x-'a'));
        int mask=0;
        long long res=0;

        unordered_map<int,int> mpp;

        for(auto c: word){
            mask^=(1 << (c-'a'));
            if(mask==desiredMask){
                res++;
            }
            if(mpp.find(desiredMask ^ mask)!=mpp.end()){
                res+=mpp[desiredMask ^ mask];
            }
            mpp[mask]++;
        }
        return res;
    }

    long long zeroXOR(string &word){
        long long res=0;
        int mask=0;

        unordered_map<int,int> mpp;

        for(auto x: word){
            mask^=(1 << (x-'a'));
            if(mask==0){
                res++;
            }
            if(mpp.find(mask)!=mpp.end()){
                res+=mpp[mask];
            }
            mpp[mask]++;
        }
        return res;
    }

    long long wonderfulSubstrings(string word) {
        long long res=0;
        for(int i=0;i<10;i++){
            res+=helper(word,i+'a');
        }
        res+=zeroXOR(word); // Because if there is no odd count of letters, XOR will be zero of the subaray
        return res;
    }
};