Count Wonderful Substrings — Bitmask + Prefix XOR Map

Problem 182 · Count Number of Wonderful Substrings

Difficulty: Medium · Pattern: Bitmask + Prefix Map

A wonderful string has at most one letter with odd frequency. Count all wonderful substrings.

Intuition

Represent letter parity as a 10-bit mask (only letters a–j). A substring is wonderful if its XOR mask has at most one set bit. Track prefix XOR counts.

Solutions

// C++
long long wonderfulSubstrings(string word) {
    unordered_map<int,int> cnt;
    cnt[0] = 1;
    long long ans = 0;
    int mask = 0;
    for (char c : word) {
        mask ^= 1 << (c - 'a');
        ans += cnt[mask]; // all-even
        for (int i = 0; i < 10; i++)
            ans += cnt[mask ^ (1 << i)]; // one odd
        cnt[mask]++;
    }
    return ans;
}

// Java
public long wonderfulSubstrings(String word) {
    Map<Integer,Integer> cnt = new HashMap<>();
    cnt.put(0, 1);
    long ans = 0; int mask = 0;
    for (char c : word.toCharArray()) {
        mask ^= 1 << (c - 'a');
        ans += cnt.getOrDefault(mask, 0);
        for (int i = 0; i < 10; i++)
            ans += cnt.getOrDefault(mask ^ (1 << i), 0);
        cnt.merge(mask, 1, Integer::sum);
    }
    return ans;
}

// JavaScript
var wonderfulSubstrings = function(word) {
    const cnt = new Map([[0, 1]]);
    let ans = 0, mask = 0;
    for (const c of word) {
        mask ^= 1 << (c.charCodeAt(0) - 97);
        ans += cnt.get(mask) || 0;
        for (let i = 0; i < 10; i++)
            ans += cnt.get(mask ^ (1 << i)) || 0;
        cnt.set(mask, (cnt.get(mask) || 0) + 1);
    }
    return ans;
};

# Python
from collections import defaultdict
def wonderfulSubstrings(word: str) -> int:
    cnt = defaultdict(int)
    cnt[0] = 1
    ans = mask = 0
    for c in word:
        mask ^= 1 << (ord(c) - ord('a'))
        ans += cnt[mask]
        for i in range(10):
            ans += cnt[mask ^ (1 << i)]
        cnt[mask] += 1
    return ans

Complexity

Time: O(10n) = O(n)
Space: O(1024) = O(1)