Number of Wonderful Substrings: Bitmask Parity Tracking

LeetCode #1915, Number of Wonderful Substrings, combines two powerful patterns into one problem: bitmask parity tracking and prefix counting. If you have worked with XOR for single-number problems or prefix sums for subarray counting, this one ties both ideas together in a satisfying way.

The problem

A wonderful string is one where at most one character appears an odd number of times. Given a string word consisting of the first ten lowercase letters ('a' through 'j'), return the number of non-empty wonderful substrings.

word = "aba"  -> 4
word = "aabb" -> 9
word = "he"   -> 2

For "aba", the four wonderful substrings are: "a", "b", "a", and "aba". Each of these has at most one character with an odd count.

The approach

The brute-force way is to check every possible substring, count character frequencies, and verify that at most one has an odd count. That is O(n^2) at best. We need something faster.

The key insight is that you do not need to track exact frequencies. You only need to know whether each character has appeared an even or odd number of times. That is a single bit of information per character, and with only 10 possible characters ('a' through 'j'), you can pack the entire parity state into a 10-bit integer.

XOR for toggling. When you encounter a character, XOR the bitmask with 1 << (ord(c) - ord('a')). This flips the corresponding bit. If the character had even parity, it becomes odd. If it had odd parity, it becomes even. You never need to count actual frequencies.

Prefix bitmask. Just like prefix sums let you compute subarray sums as differences, prefix bitmasks let you compute substring parity as XOR differences. If the prefix bitmask at position j is mask_j and the prefix bitmask at position i is mask_i, then the parity of the substring from i+1 to j is mask_j XOR mask_i.

What makes a wonderful substring? The XOR of two prefix bitmasks must be either:

• 0 (all characters have even frequency), or
• A value with exactly one bit set (exactly one character has odd frequency)

Counting matches. For each position, you check: how many previous prefix bitmasks are equal to the current mask (XOR is 0, meaning all even)? And how many differ by exactly one bit (try flipping each of the 10 bits)? A hash map that counts how many times each prefix bitmask has appeared gives you the answer in O(1) per check.

def wonderful_substrings(word: str) -> int:
    count = {0: 1}
    mask = 0
    result = 0

    for c in word:
        mask ^= 1 << (ord(c) - ord('a'))
        result += count.get(mask, 0)
        for i in range(10):
            result += count.get(mask ^ (1 << i), 0)
        count[mask] = count.get(mask, 0) + 1

    return result

Step-by-step walkthrough

Let's trace through word = "aba". The answer is 4.

At each position, we XOR the current character into the bitmask, then check the count map for exact matches (all even frequencies) and single-bit-flip matches (exactly one odd frequency). The total across all positions gives us the final answer.

Complexity analysis

Time: O(n). For each character, you do one XOR, one hash map lookup for exact match, and 10 hash map lookups for single-bit flips. That is 11 constant-time operations per character, so the total is O(11n) = O(n).

Space: O(1). The bitmask has at most 2^10 = 1024 possible values, so the hash map never grows beyond 1024 entries. This is constant with respect to the input size.

The Building Blocks

This problem combines two reusable patterns that CodeBricks drills independently:

Bitmask parity tracking

Use a bitmask where each bit represents even/odd parity for one character. XOR toggles the bit when you see that character. This reduces character frequency tracking to a single integer operation.

mask = 0
for c in word:
    mask ^= 1 << (ord(c) - ord('a'))

This micro-pattern appears whenever a problem cares about parity (even vs. odd counts) rather than exact frequencies. It is the foundation of problems involving palindrome rearrangements, wonderful strings, and frequency-based substring queries.

Prefix counting with a hash map

Store how many times each prefix state has occurred. For each new position, query the map to count how many previous states satisfy your condition, then record the current state. This is the same structure as Subarray Sum Equals K, but with bitmasks instead of sums.

count = {initial_state: 1}
for item in sequence:
    update(state)
    result += count.get(target_state, 0)
    count[state] = count.get(state, 0) + 1

When you can fluently apply both patterns, this problem becomes a direct combination of the two. You stop thinking about substring enumeration and start thinking in terms of prefix bitmask differences.

Edge cases to watch for

Single character string. The string "a" has exactly one wonderful substring: "a" itself. The mask becomes 1, and mask ^ (1 << 0) = 0 is in the count map. The algorithm returns 1 correctly.

All same characters. For a string like "aaaa", every substring is wonderful. Substrings of even length have all-even frequencies. Substrings of odd length have exactly one character with odd frequency. The bitmask alternates between 0 and 1, and the count map accumulates matches at each step.

All distinct characters. A string like "abcdefghij" (all 10 distinct letters) still works. Each character sets a new bit. The algorithm checks all 10 single-bit flips at each position to find substrings with at most one odd character.

Long strings. The time complexity is O(n) with a small constant factor (11 hash map lookups per character). Even for strings near the constraint limit of 10^5 characters, this runs efficiently. The hash map stays bounded at 1024 entries regardless of input length.

From understanding to recall

The bitmask parity approach is elegant once you see it. But combining XOR toggling, prefix counting, and the 10-bit flip check into one solution requires practice. In an interview, you need all three pieces to come together smoothly.

Spaced repetition helps you internalize the connection between parity, bitmasks, and prefix maps. You drill the pattern as an isolated building block, then combine it with prefix counting in full problem contexts. After a few rounds, the insight that "parity tracking = bitmask, substring counting = prefix map" fires automatically when you read the problem statement.

Related posts

• Single Number - XOR cancellation in its simplest form. The same XOR toggle mechanic powers both problems, but here you track parity across characters instead of cancelling duplicates.
• Subarray Sum Equals K - The prefix sum + hash map pattern that this problem adapts. Instead of prefix sums, you use prefix bitmasks. Instead of checking one difference, you check 11.
• Hash Map Patterns - A broader look at how hash maps enable constant-time lookups that transform quadratic algorithms into linear ones.

CodeBricks uses spaced repetition to help you internalize patterns like bitmask parity tracking. Instead of re-reading solutions, you practice writing them from scratch at increasing intervals. Each review strengthens the connection between "at most one odd character" and "bitmask prefix counting." Over time, the pattern becomes second nature.