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.

&nbsp;
Example 1:

Input: word = "aba"
Output: 4
Explanation: The four wonderful substrings are underlined below:
- "aba" -&gt; "a"
- "aba" -&gt; "b"
- "aba" -&gt; "a"
- "aba" -&gt; "aba"


Example 2:

Input: word = "aabb"
Output: 9
Explanation: The nine wonderful substrings are underlined below:
- "aabb" -&gt; "a"
- "aabb" -&gt; "aa"
- "aabb" -&gt; "aab"
- "aabb" -&gt; "aabb"
- "aabb" -&gt; "a"
- "aabb" -&gt; "abb"
- "aabb" -&gt; "b"
- "aabb" -&gt; "bb"
- "aabb" -&gt; "b"


Example 3:

Input: word = "he"
Output: 2
Explanation: The two wonderful substrings are underlined below:
- "he" -&gt; "h"
- "he" -&gt; "e"


&nbsp;
Constraints:


	1 &lt;= word.length &lt;= 105
	word consists of lowercase English letters from 'a'&nbsp;to 'j'.

class Solution:
    def wonderfulSubstrings(self, word: str) -> int:
        cnt, res, mask = [1] + [0] * 1023, 0, 0
        for ch in word:
            mask ^= 1 << (ord(ch) - ord('a'))
            res += cnt[mask]
            for n in range(10):
                res += cnt[mask ^ 1 << n];
            cnt[mask] += 1
        return res
class Solution {
    public long wonderfulSubstrings(String word) {
        int n = word.length();
        long count = 0;
        
        long[] freq = new long[(1 << 10) + 1]; // Since we have to take only 2^10 possibilies, we can avoid an HashMap
        
        freq[0] = 1;
        int res = 0; // initialize the frequency of 0000000000 as 1 because when no element is encountered, then th bitmask is 0
        
        for (int i = 0; i < n; i++) {
            int mask = (1 << (word.charAt(i) - 'a'));
            res ^= mask; // toggling bit of the current character to make it from odd to even OR even to odd
            int chkMask = 1;
            
            count += freq[res];
            for (int j = 1; j <= 10; j++) {  // Loop for checking all possiblities of different places of the Different Bit
                count += freq[chkMask ^ res];
                chkMask <<= 1;
            }
            
            freq[res]++; // increasing the frequency of the current bitmask
        }
        
        return count;
    }
}
class Solution {
public:
    long long wonderfulSubstrings(string word) {
        int n=word.length();
        int mask=0;
        unordered_map<int,int>m;
        m[0]++;
        long long int ans=0;
        for(int i=0;i<n;i++){
            mask = mask^(1<<(word[i]-'a'));
            int temp=mask;
            int j=0;
            while(j<=9){
               int x=temp^(1<<j);
                ans+=m[x];
                j++;

            }
            ans+=m[mask];
            m[mask]++;
        }

        return ans;

    }
};
/**
 * @param {string} word
 * @return {number}
 */
var wonderfulSubstrings = function(word) {
    let hashMap={},ans=0,binaryRepresentation=0,t,pos,number,oneBitToggled;
    hashMap[0]=1;
    for(let i=0;i<word.length;i++){
        pos = word[i].charCodeAt(0)-"a".charCodeAt(0);//Let's use position 0 for a, 1 for b .... 9 for j
        t = (1 << pos);
        binaryRepresentation = (binaryRepresentation^t);//Toggle the bit at pos in the current mask(pattern)
        //This loop will check same binaryRepresentation and all the other binaryRepresentation with difference of 1 bit
        for(let i=0;i<10;i++){//Check all the numbers by changing 1 position
            number = (1<<i);//Change 1 bit at a time 
            oneBitToggled = (binaryRepresentation^number);
            if(hashMap[oneBitToggled]!==undefined){
                ans += hashMap[oneBitToggled];
            }
        }
        if(hashMap[binaryRepresentation]===undefined){
            hashMap[binaryRepresentation]=1;
        }else{
            ans += hashMap[binaryRepresentation];
            hashMap[binaryRepresentation]++;
        }
    }
    return ans;
};
Number of Wonderful Substrings