<p>A <strong>wonderful</strong> string is a string where <strong>at most one</strong> letter appears an <strong>odd</strong> number of times.</p>

<ul>
	<li>For example, <code>&quot;ccjjc&quot;</code> and <code>&quot;abab&quot;</code> are wonderful, but <code>&quot;ab&quot;</code> is not.</li>
</ul>

<p>Given a string <code>word</code> that consists of the first ten lowercase English letters (<code>&#39;a&#39;</code> through <code>&#39;j&#39;</code>), return <em>the <strong>number of wonderful non-empty substrings</strong> in </em><code>word</code><em>. If the same substring appears multiple times in </em><code>word</code><em>, then count <strong>each occurrence</strong> separately.</em></p>

<p>A <strong>substring</strong> is a contiguous sequence of characters in a string.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> word = &quot;aba&quot;
<strong>Output:</strong> 4
<strong>Explanation:</strong> The four wonderful substrings are underlined below:
- &quot;<u><strong>a</strong></u>ba&quot; -&gt; &quot;a&quot;
- &quot;a<u><strong>b</strong></u>a&quot; -&gt; &quot;b&quot;
- &quot;ab<u><strong>a</strong></u>&quot; -&gt; &quot;a&quot;
- &quot;<u><strong>aba</strong></u>&quot; -&gt; &quot;aba&quot;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> word = &quot;aabb&quot;
<strong>Output:</strong> 9
<strong>Explanation:</strong> The nine wonderful substrings are underlined below:
- &quot;<strong><u>a</u></strong>abb&quot; -&gt; &quot;a&quot;
- &quot;<u><strong>aa</strong></u>bb&quot; -&gt; &quot;aa&quot;
- &quot;<u><strong>aab</strong></u>b&quot; -&gt; &quot;aab&quot;
- &quot;<u><strong>aabb</strong></u>&quot; -&gt; &quot;aabb&quot;
- &quot;a<u><strong>a</strong></u>bb&quot; -&gt; &quot;a&quot;
- &quot;a<u><strong>abb</strong></u>&quot; -&gt; &quot;abb&quot;
- &quot;aa<u><strong>b</strong></u>b&quot; -&gt; &quot;b&quot;
- &quot;aa<u><strong>bb</strong></u>&quot; -&gt; &quot;bb&quot;
- &quot;aab<u><strong>b</strong></u>&quot; -&gt; &quot;b&quot;
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> word = &quot;he&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> The two wonderful substrings are underlined below:
- &quot;<b><u>h</u></b>e&quot; -&gt; &quot;h&quot;
- &quot;h<strong><u>e</u></strong>&quot; -&gt; &quot;e&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= word.length &lt;= 10<sup>5</sup></code></li>
	<li><code>word</code> consists of lowercase English letters from <code>&#39;a&#39;</code>&nbsp;to <code>&#39;j&#39;</code>.</li>
</ul>
// Sure! Let’s break it down in simpler terms:

// The goal is to count how many "wonderful" substrings exist in a given string. A "wonderful" substring is defined as a string where:

// Either all letters appear an even number of times, OR
// Exactly one letter appears an odd number of times, and the rest appear an even number of times.
// Key Ideas:
// Bitmasking:

// Imagine we keep track of each letter in the string using a series of 10 "switches" (or bits), one for each letter from 'a' to 'j'.
// These "switches" tell us if the number of times a letter has appeared is odd or even.
// For example, if we see an 'a' once, the switch for 'a' flips to "on" (odd). If we see it again, it flips back to "off" (even).
// Prefix Approach:

// Instead of looking at all possible substrings (which would be slow), we use the idea of prefixes.
// A prefix is a part of the string from the beginning up to some point. We keep track of the switches (or "mask") as we move through the string.
// If two different prefixes have the same set of switches, the substring between them must have all letters appearing an even number of times. This is because the changes between the two prefixes cancel each other out.
// Step-by-Step Explanation:
// Initial Setup:

// We have a mask, which starts at 0. This mask keeps track of whether the letters we've seen so far appear an odd or even number of times.
// We also have a freq map that keeps track of how often each mask has appeared.
// Processing Each Letter:

// As we move through the string letter by letter:
// We update the mask for that letter. If the letter appears an odd number of times, the bit for that letter is flipped "on". If it appears an even number of times, the bit is flipped "off".
// After updating the mask, we check how many times this exact mask has appeared before. If it has appeared before, then all the letters between that point and the current point must have appeared an even number of times, so we count those substrings.
// Checking Substrings with One Odd Letter:

// In addition to checking for all-even substrings, we also check for substrings where exactly one letter appears an odd number of times.
// To do this, we flip one bit at a time in the mask and check how many times a mask with that one odd letter has appeared.
// Return the Result:

// At the end, we return the total number of wonderful substrings we've found.
// Example:
// Suppose the string is "aba":

// Start with an empty string (prefix), and its bitmask is 0000000000 (all even).
// As you go through the string:
// You see 'a', and the bitmask becomes 0000000001 (since 'a' has appeared once, odd).
// Then you see 'b', and the bitmask becomes 0000000011 (now both 'a' and 'b' are odd).
// Finally, you see 'a' again, and the bitmask becomes 0000000010 (since 'a' has appeared an even number of times now).
// At each step, the code checks if these masks have appeared before and counts how many substrings are "wonderful."

// The bitmasking approach helps check the substring conditions efficiently without having to manually count every character in every substring.
class Solution {
public:
    long long wonderfulSubstrings(string word) {
        int N = word.length();
        
        // Create the frequency map
        // Key = bitmask, Value = frequency of bitmask key
        unordered_map<int, int> freq;

        // The empty prefix can be the smaller prefix, which is handled like this
        freq[0] = 1;

        int mask = 0;
        long long res = 0;
        for (int i = 0; i < N; i++) {
            char c = word[i];
            int bit = c - 'a';

            // Flip the parity of the c-th bit in the running prefix mask
            mask ^= (1 << bit);
            
            // Count smaller prefixes that create substrings with no odd occurring letters
            res += freq[mask];

            // Increment value associated with mask by 1
            freq[mask]++;

            // Loop through every possible letter that can appear an odd number of times in a substring
            for (int odd_c = 0; odd_c < 10; odd_c++) {
                res += freq[mask ^ (1 << odd_c)];
            }
        }
        return res;

    }
};
20200