Number of Wonderful Substrings

Problem Description

A wonderful string is a string where at most one letter appears an odd number of times. Given a string word that consists of the first ten lowercase English letters (from 'a' to '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.

Key Insights

• A substring is wonderful if at most one character in it has an odd frequency.
• We can represent the frequency of characters using a bitmask to track odd/even counts for the 10 characters ('a' to 'j').
• By using prefix sums and a hash table, we can efficiently count the number of wonderful substrings.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) (for the bitmask, since it has a fixed size)

Solution

To solve the problem, we will use a bitmask to represent the frequency of each character in the string. Each bit in the bitmask will indicate whether the corresponding character (from 'a' to 'j') has an odd count (1) or even count (0).

1. Initialize a hash table to keep track of the frequency of each bitmask.
2. Traverse the string, updating the bitmask as we include each character.
3. For each prefix bitmask, check how many previous masks match the current mask or differ by exactly one bit (indicating one odd character).
4. Count those valid substrings and update the hash table with the current mask.

This approach allows us to efficiently count all wonderful substrings using bit manipulation and prefix sums.

Code Solutions