Solution: Number of Wonderful Substrings

Statement

A wonderful string is defined as a string in which at most one letter occurs an odd number of times.

For example:

• The string “aabbc” is wonderful because only the letter 'c' appears an odd number of times.

• The string “pqpq” is wonderful because all letters appear an even number of times.

• The string “mn” is not wonderful because both 'm' and 'n' appear an odd number of times.

You are given a string word that consists of lowercase English letters from 'a' to 'j'. Your task is to return the total number of wonderful non-empty substringsA substring is any contiguous sequence of characters within the string. in word.

Note: If a substring appears multiple times, each occurrence should be counted separately.

Constraints:

• $1 <=$ word.length $<= 10^3$

• word consists of lowercase English letters from 'a' to 'j'.

Solution

The solution uses a hash map to count the number of wonderful substrings in a given string word. A wonderful substring is defined as a string in which at most one letter appears an odd number of times. The approach leverages a bitmask to track the parity of character frequencies efficiently.

Let’s go through the steps of the solution:

1. We create a hash map called freq to store the frequency of each bitmask. Each key in this hash map represents a bitmask that corresponds to the characters in the substring, while the value represents how many times that bitmask has been encountered.

2. We initialize freq[0] = 1, where $0$ represents an empty prefix, which serves as a base case.

3. We create a variable mask to maintain the current bitmask representing the frequency of characters as we iterate through the string.

4. We also initialize a variable res with $0$ to store the count of wonderful substrings.

5. We iterate through each character in word. For each character:

   1. We calculate the corresponding bit position, which gives us a value between $0$ and $9$ for letters 'a' to 'j'( since 'a' corresponds to $0$ and 'j' corresponds to $9$).

   2. We flip the parity of the bit at the calculated position in the mask using the XOR operation.

6. After updating the mask, we count substrings with zero odd occurrences by checking if the current mask exists in the frequency map freq.

   1. If it does:

      1. We add the count of that bitmask to res, which indicates the number of wonderful substrings ending at the current character.

      2. We then increment the count of the current mask in freq.

   2. If it doesn’t exist, we initialize it with a value of $1$.

7. To account for substrings that can have exactly one character with an odd count, we iterate through each possible character that could be odd (from $0$ to $9$). For each character:

   1. We check if toggling its corresponding bit in the mask (using XOR again) results in a bitmask that exists in freq. If it does, we add the frequency of that altered bitmask to res.

8. Finally, after processing all characters in the string, we return res, which contains the total number of wonderful substrings found in word.

Let’s look at the following illustration to get a better understanding of the solution: