LeetCode 1915. Number of Wonderful Substrings

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.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• 1 <= word.length <= 105
• word consists of lowercase English letters from 'a' to 'j'.

Solution

So solve this problem, we need to know a few things

1. We can represent the odd/evenness of a string with a bitmask

First we count the number of occurrences of each character in the string. Then if we convert the count to binary 0 = even, 1 = odd since all we care about is even or odd not the actual count.

If you need a refresher for bitmask, check out this tutorial.

2. In terms of bitmask calculations, appending a character to a string is equivalent to doing an XOR operation of the bitmask of the character and the bitmask of string. Quick review of XOR: it returns 1 if the bits are different, 0 if they are the same. Adding a character to a string flips the even/odd bit for that character in the bitmask.

3. If the prefix of a string has the same bitmask as the string, then the remaining substring’s bitmask has all its bits 0 and is a wonderful string.

With the knowledge under our belt, we can now go through each character of the string compute the bitmask using 2) and test if a matching prefix using 3) and add to result. This handles all the cases where occurrence of all characters are even.

We also want to add the case where one character appears odd number of times. We can do this by flipping the bit for each character in the current string and if the resulting bitmask exist as a prefix then add the count to the result.

class Solution:
    def wonderfulSubstrings(self, word: str) -> int:
        # count is a bitmask where each bit represent the count of a character from a-j % 2
        # bitmask is 10 bits, each bit 2 values, 2^10 = 1024
        count = [0] * 1024
        # 0 means empty string, which has all its bits 0
        count[0] = 1
        ans = 0
        cur = 0
        for char in word:
            # bitmask of the current string ending in char
            cur ^= 1 << (ord(char) - ord('a'))
            # add the all even case to result
            ans += count[cur]
            # flip each bit and see if there's matching prefix
            # this adds the 'at most one' odd case.
            for i in range(10):
                new_bitmask = cur ^ (1 << i)
                if count[new_bitmask] > 0:
                    ans += count[new_bitmask]
            count[cur] += 1
        return ans