Count Wonderful Substrings — Bitmask XOR and Prefix Parity Maps

Problem Statement#

A wonderful string is a string where at most one letter has an odd number of occurrences. Count the number of wonderful non-empty substrings of word. The string consists only of the first 10 lowercase letters 'a' to 'j'.

Constraints:

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

Example 1:
Input:  word = "aba"
Output: 4
Explanation: Wonderful substrings: "a", "b", "a", "aba".
             "ab" has one odd char (a:1, b:1 — two odd), not wonderful.
             "ba" similarly not wonderful.

Example 2:
Input:  word = "aabb"
Output: 9
Explanation: Wonderful substrings: "a","b","b","aa","bb","aab" (a:2,b:1→1 odd),"abb"(a:1,b:2→1 odd),"aabb","b" → 9 total.

Example 3:
Input:  word = "he"
Output: 2
Explanation: "h" and "e" are both wonderful (each has exactly 1 character appearing once — 1 odd).

Why This Problem Matters#

Count Wonderful Substrings is an advanced problem that sits at the intersection of bit manipulation, prefix XOR, and hash maps. Google and Meta use this problem for senior-level screening because it requires three independent insights to work together: (1) representing character parity as a bitmask, (2) tracking prefix XOR to determine substring parity, and (3) using a hash map to count how many previous prefix states lead to a wonderful substring.

This problem cannot be solved efficiently with standard frequency counting alone — the key is to reduce the "frequency parity" question (is the frequency of each character even or odd?) to a bitmask problem. By representing the parity state of 10 characters as a 10-bit mask, the question "does the substring have at most one character with odd frequency?" becomes "does the XOR of the prefix bitmasks have at most one bit set?" This transforms a complex frequency comparison into a simple bitmask check.

The bitmask XOR trick for tracking substring parities is a powerful technique. It appears in problems like "find the number of subarrays with XOR equal to k," "count subarrays with balanced brackets," and "detect even/odd parity in subsets." Mastering it here prepares you for a broad class of hard problems where character or element parity is the key property.

The specific structure of this problem — 10 characters, 2^10 = 1024 possible bitmask states — makes the hash map approach very efficient. The state space is bounded at 1024, so the map never has more than 1024 entries, giving O(1) amortized space per character.

The Core Insight#

Represent character parity as a bitmask. Use a 10-bit integer where bit i is 1 if character 'a' + i has appeared an odd number of times so far, and 0 if even. XOR the bit for character c whenever c is encountered: mask ^= (1 << (ord(c) - ord('a'))).

Prefix XOR for substring parity. If prefix_mask[j] is the parity mask of word[0..j], then the parity mask of substring word[i+1..j] is prefix_mask[j] XOR prefix_mask[i]. This follows because XOR is its own inverse: characters appearing in both [0..i] and [0..j] cancel out.

Wonderful substring condition. A substring is wonderful if its parity mask has at most one bit set — i.e., at most one character has odd frequency. This means the XOR of the two prefix masks equals 0 (all even frequencies) or exactly one power of 2 (exactly one odd frequency).

Count valid previous prefix masks. For each position j with prefix mask mask:

1. Count previous positions where mask_i == mask (gives all-even substring — wonderful).
2. For each bit b in [0, 9], count positions where mask_i == mask XOR (1 << b) (gives exactly one odd frequency — wonderful).

Use a hash map cnt[mask] to track how many times each prefix mask has been seen. Total wonderful substrings ending at j = cnt[mask] + sum(cnt[mask ^ (1 << b)] for b in range(10)).

Visual Dry Run#

Input: word = "aba"

Initialize: mask = 0, cnt = {0: 1}, answer = 0

Character 'a' (index 0): mask = 0 XOR (1 << 0) = 1 (bit 0 set: 'a' has odd count)

Lookup for wonderful substrings ending here:

• cnt[1] (all-even XOR) = 0
• cnt[1 ^ 1] = cnt[0] (flip bit 0) = 1 → substring "a" is wonderful ✓
• cnt[1 ^ 2] = 0, ..., cnt[1 ^ 512] = 0

answer += 1. cnt[1] += 1 → cnt = {0:1, 1:1}

Character 'b' (index 1): mask = 1 XOR (1 << 1) = 3 (bits 0 and 1 set: 'a' odd, 'b' odd)

Lookup:

• cnt[3] = 0
• cnt[3 ^ 1] = cnt[2] = 0
• cnt[3 ^ 2] = cnt[1] = 1 → substring "b" is wonderful ✓ (parity mask 3 XOR 1 = "b" alone: a:0,b:1)
• Other flips: all 0

answer += 1 = 2. cnt[3] = 1 → cnt = {0:1, 1:1, 3:1}

Character 'a' (index 2): mask = 3 XOR 1 = 2 (bit 1 set only: 'b' has odd count, 'a' now even)

Lookup:

• cnt[2] = 0
• cnt[2 ^ 1] = cnt[3] = 1 → wonderful substring: from some start to index 2
• cnt[2 ^ 2] = cnt[0] = 1 → wonderful (all-even): "aba" itself ✓
• Other flips: 0

answer += 2 = 4.

Final answer: 4. Correct!

Solution (Optimal)#

from collections import defaultdict
 
def wonderfulSubstrings(word: str) -> int:
    # cnt[mask] = number of times this prefix parity mask has been seen
    cnt = defaultdict(int)
    cnt[0] = 1  # Empty prefix has mask 0 (all even)
 
    mask = 0     # Current prefix parity mask
    answer = 0
 
    for ch in word:
        # Update prefix mask: flip the bit for this character
        mask ^= 1 << (ord(ch) - ord('a'))
 
        # Case 1: All characters in substring have even frequency
        # (current mask == some previous mask → XOR = 0)
        answer += cnt[mask]
 
        # Case 2: Exactly one character has odd frequency
        # (current mask XOR previous mask has exactly one bit set)
        for bit in range(10):
            answer += cnt[mask ^ (1 << bit)]
 
        # Record this prefix mask
        cnt[mask] += 1
 
    return answer

var wonderfulSubstrings = function(word) {
    // Map from prefix parity mask to count of occurrences
    const cnt = new Map([[0, 1]]);
 
    let mask = 0;
    let answer = 0;
 
    for (const ch of word) {
        // Update prefix mask
        mask ^= 1 << (ch.charCodeAt(0) - 97);
 
        // All-even case: current mask was seen before
        answer += cnt.get(mask) || 0;
 
        // Exactly-one-odd case: flip each bit and check
        for (let bit = 0; bit < 10; bit++) {
            answer += cnt.get(mask ^ (1 << bit)) || 0;
        }
 
        // Record this prefix mask
        cnt.set(mask, (cnt.get(mask) || 0) + 1);
    }
 
    return answer;
};

Complexity Analysis

The bitmask approach is optimal. Each character requires one mask update and 11 hash map lookups (1 for all-even + 10 for exactly-one-odd). The map has at most 2^10 = 1024 entries. Both time and space are effectively O(n).

Common Mistakes#

• Forgetting the cnt[0] = 1 initialization. The empty prefix (before any character) has mask 0. Without this initialization, substrings starting at index 0 that are wonderful (parity XOR with the empty prefix is wonderful) are not counted.
• Mixing up XOR with AND. XOR of two prefix masks gives the parity of the substring between them. AND does not serve this purpose.
• Checking mask ^ (1 << bit) == 0 instead of looking up cnt[mask ^ (1 << bit)]. You want the count of prefix positions with that mask, not whether that mask is zero.
• Using 26 bits instead of 10. The problem specifies only the first 10 letters ('a' to 'j'). Using 26 bits works correctly (the extra bits stay 0) but is slightly wasteful.
• Updating cnt[mask] before the lookups. You must look up the complement masks before inserting the current mask. If you insert first, you might count the current position as a valid previous prefix, which is semantically incorrect (a substring from position i to i has zero length — not counted).

Follow-up Questions#

Why is it valid to represent parity as a bitmask? The parity of a character's frequency (odd or even) is exactly the information captured by 1 or 0. XOR toggles between these states. Since we only care about parity (odd/even), not the actual count, bitmasks are the perfect representation.

How many distinct bitmask states can occur? At most 2^10 = 1024 distinct states, since there are 10 characters each with a binary parity. The hash map has a bounded maximum size of 1024.

What if the string contains all 26 letters? Use a 26-bit mask instead of 10-bit. The algorithm is identical; only the mask width and the inner loop range change (0 to 26 instead of 0 to 10).

How does the "exactly one bit set" check work mathematically? A mask with exactly one bit set is a power of 2: 1, 2, 4, 8, ..., 512 for 10 bits. Alternatively, n & (n-1) == 0 checks if n is a power of 2 (or zero). This can replace the inner loop: instead of looping over 10 bits, compute the XOR of two prefix masks and check if it is 0 or a power of 2. This is a O(1) check per lookup instead of O(10), but the savings are constant and the code is less readable.

Can this approach be extended to "at most k characters with odd frequency"? Yes, but the complexity increases. For "exactly k bits set," you need to enumerate all C(10, k) combinations of k bits and check each, which is C(10, k) lookups per character. For k = 1, that is 10 lookups. For k = 2, that is 45. Still O(n) total.

Key Takeaways#

• LC 1915 Count Wonderful Substrings encodes character parity as a 10-bit bitmask (one bit per allowed letter a..j).
• A "wonderful" substring has 0 or 1 bit set in its parity bitmask — equivalent to at most one odd-frequency letter.
• For each prefix mask m, the answer adds freq[m] (zero-bit case) plus sum(freq[m XOR (1 << i)] for i in 0..9) (one-bit cases).
• Seed the parity-frequency map with {0: 1} to handle prefixes that themselves are wonderful.
• Time O(n * 10) = O(n); space O(2^10) = O(1) — both optimal.
• Bitmask XOR is the right choice anytime "even/odd parity of multiple categories" is the invariant.
• Same prefix-XOR pattern powers LC 1371, LC 1542, and many parity-flip subarray problems.

Related Problems#

• LC 1915 — Count Wonderful Substrings: This problem.
• LC 1371 — Find the Longest Substring Containing Vowels in Even Counts: Same bitmask prefix XOR technique — find the longest substring where all specified characters have even frequency.
• LC 1542 — Find Longest Awesome Substring: Similar bitmask approach for palindrome-possible substrings.
• LC 560 — Subarray Sum Equals K: Prefix sum complement map — same structural pattern but with integer sums instead of bitmasks.
• LC 523 — Continuous Subarray Sum: Prefix modulo map — same "complement lookup" structure.
• LC 421 — Maximum XOR of Two Numbers in an Array: Bitmask manipulation on numbers — related XOR reasoning.