Number Of Wonderful Substrings - Leetcode Solution

Number of Wonderful Substrings is a problem on LeetCode that asks you to find the number of non-empty substrings of a string s, such that each character appears an even number of times.

To solve this problem, we can use a bitmask to keep track of the parity of each character in a substring. Let us consider the i-th character of s. Its parity can be represented by a bitmask of length 10, where the j-th bit is set to 1 if the frequency of the j-th letter in the substring is odd, and 0 otherwise.

For example, if we are looking at the substring "abbccc", the bitmask for 'a' would be 001, the bitmask for 'b' would be 010, and the bitmask for 'c' would be 100.

We can use a hash table to keep track of the number of substrings with each bitmask. To count the number of wonderful substrings, we can iterate through the string s and update the hash table as follows:

1. Initialize the hash table with a count of 1 for the bitmask of length 10 with all bits set to 0.

2. For each index i in s, compute the bitmask for the substring s[0:i] using the parity of each character, and add the count of substrings with this bitmask to the answer. Then update the hash table by incrementing the count of substrings with this bitmask by 1.

3. Return the answer.

Here is the Python code that implements this algorithm:

class Solution:
    def wonderfulSubstrings(self, s: str) -> int:
        count = {0: 1}  # initialize hash table with count of 1 for bitmask 0
        ans, mask = 0, 0
        for c in s:
            index = ord(c) - ord('a')
            mask ^= (1 << index)  # toggle j-th bit in mask
            ans += count.get(mask, 0)  # add count of substrings with this bitmask to answer
            for j in range(10):
                new_mask = mask ^ (1 << j)  # toggle j-th bit in mask
                ans += count.get(new_mask, 0)  # add count of substrings with this bitmask to answer
            count[mask] = count.get(mask, 0) + 1  # update count for current bitmask
        return ans

The time complexity of this algorithm is O(n * 10), where n is the length of the string s, since we iterate through the string once and update the hash table for each character with a bitmask of length 10. The space complexity is also O(n * 10), since the hash table can have up to n * 10 entries.

1