Number of Wonderful Substrings — DSA

Problem#

A “wonderful” string has at most one letter appearing an odd number of times. Given a string word of letters 'a'..'j', count the number of non-empty substrings that are wonderful.

Examples#

word = "aba" → 4 ("a", "b", "a", "aba").
word = "aabb" → 9.

Constraints#

1 <= word.length <= 10^5, characters from 'a' to 'j'.

Hints#

Hint 1

Use a 10-bit mask tracking parity of each letter’s count in the prefix.

Hint 2

A substring is wonderful iff its mask differs from a previous prefix mask in 0 or 1 bits.

Approach#

Prefix bitmask m toggles bit c - 'a' on each character. For each new m, count: (a) prior occurrences of the same m (zero odd letters) and (b) prior occurrences of m ^ (1 << k) for each k (exactly one odd letter). Store mask occurrences in a fixed int[1024]. Initialize freq[0] = 1 to count substrings starting at index 0.

Solution#

class Solution {
public:
    long long wonderfulSubstrings(string word) {
        long long ans = 0;
        int freq[1024] = {0};
        freq[0] = 1;
        int mask = 0;
        for (char c : word) {
            mask ^= 1 << (c - 'a');
            ans += freq[mask];
            for (int k = 0; k < 10; ++k) ans += freq[mask ^ (1 << k)];
            ++freq[mask];
        }
        return ans;
    }
};

func wonderfulSubstrings(word string) int64 {
    var ans int64
    var freq [1024]int64
    freq[0] = 1
    mask := 0
    for i := 0; i < len(word); i++ {
        mask ^= 1 << (word[i] - 'a')
        ans += freq[mask]
        for k := 0; k < 10; k++ {
            ans += freq[mask^(1<<k)]
        }
        freq[mask]++
    }
    return ans
}

class Solution:
    def wonderfulSubstrings(self, word: str) -> int:
        ans = 0
        freq = [0] * 1024
        freq[0] = 1
        mask = 0
        for ch in word:
            mask ^= 1 << (ord(ch) - ord('a'))
            ans += freq[mask]
            for k in range(10):
                ans += freq[mask ^ (1 << k)]
            freq[mask] += 1
        return ans

function wonderfulSubstrings(word) {
    let ans = 0;
    const freq = new Array(1024).fill(0);
    freq[0] = 1;
    let mask = 0;
    for (let i = 0; i < word.length; i++) {
        mask ^= 1 << (word.charCodeAt(i) - 97);
        ans += freq[mask];
        for (let k = 0; k < 10; k++) {
            ans += freq[mask ^ (1 << k)];
        }
        freq[mask]++;
    }
    return ans;
}

class Solution {
    public long wonderfulSubstrings(String word) {
        long ans = 0;
        long[] freq = new long[1024];
        freq[0] = 1;
        int mask = 0;
        for (int i = 0; i < word.length(); i++) {
            mask ^= 1 << (word.charAt(i) - 'a');
            ans += freq[mask];
            for (int k = 0; k < 10; k++) {
                ans += freq[mask ^ (1 << k)];
            }
            freq[mask]++;
        }
        return ans;
    }
}

function wonderfulSubstrings(word: string): number {
    let ans = 0;
    const freq: number[] = new Array(1024).fill(0);
    freq[0] = 1;
    let mask = 0;
    for (let i = 0; i < word.length; i++) {
        mask ^= 1 << (word.charCodeAt(i) - 97);
        ans += freq[mask];
        for (let k = 0; k < 10; k++) {
            ans += freq[mask ^ (1 << k)];
        }
        freq[mask]++;
    }
    return ans;
}

Editorial#

Parity-bitmask is the canonical trick for “at most k odd counts.” The mask of any substring word[i..j] is prefix[j+1] XOR prefix[i]; wonderful means this XOR is 0 (no odd letters) or a power of two (exactly one odd). We sweep prefixes left to right, accumulating answers from the 11 relevant prior masks at each step.

Complexity#

Time: O(N * 10).
Space: O(2^10) = O(1).

Concept revision#

Continuous Subarray Sum

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#