Number of Wonderful Substrings — Medium Problem & Solution

A string is wonderful if at most one of its letters occurs an odd number of times. The letters are drawn from a through j.

Difficulty: Medium
Topics: Strings, Hash Table, Bit Manipulation, Prefix Sum
Asked at: Amazon, Google, Meta
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A string is wonderful if at most one of its letters occurs an odd number of times. The letters are drawn from a through j.

Return the number of wonderful non-empty substrings of word. Substrings at different positions count separately.

Example 1

Input: word = "aba"
Output: 4
Explanation: The wonderful substrings are "a", "b", "a" and "aba".

Example 2

Input: word = "aabb"
Output: 9

Example 3

Input: word = "he"
Output: 2
Explanation: Each single character is wonderful; "he" has two odd counts.

Constraints

1 <= word.length <= 1000
word consists of letters from a to j.

How to solve Number of Wonderful Substrings

Track a 10-bit parity mask. A substring's letter parities are the XOR of the masks at its ends, so 'at most one odd letter' means that XOR is zero or a single bit — eleven possibilities to look up per position.

Approach

Keep count[1024], seeded with count[0] = 1 for the empty prefix.
Sweep the string, toggling the bit of each letter into state.
Add count[state] (zero odd letters) and count[state ^ (1 << b)] for each of the ten bits (exactly one odd letter).
Increment count[state] and continue.

Why it works

For a substring ending at the current index and starting after an earlier prefix, the parity pattern is state ^ earlierState. That has at most one set bit exactly when earlierState equals state or differs from it in one position — which is precisely the eleven lookups.

Complexity

Time — O(n · 10)
Space — O(1024)

Pitfalls

Omitting the count[0] = 1 seed drops every substring that starts at index 0.
Incrementing count[state] before the lookups counts the current prefix against itself.
At LeetCode's real length limit the answer exceeds 32 bits; this version caps the length so it fits.

Reference solution

Python

def wonderfulSubstrings(word: str) -> int:
    count = [0] * 1024
    count[0] = 1
    state = 0
    total = 0
    for ch in word:
        state ^= 1 << (ord(ch) - 97)
        total += count[state]
        for b in range(10):
            total += count[state ^ (1 << b)]
        count[state] += 1
    return total

JavaScript

var wonderfulSubstrings = function(word) {
    var count = [];
    for (var t = 0; t < 1024; t++) count.push(0);
    count[0] = 1;
    var state = 0, total = 0;
    for (var i = 0; i < word.length; i++) {
        state ^= 1 << (word.charCodeAt(i) - 97);
        total += count[state];
        for (var b = 0; b < 10; b++) total += count[state ^ (1 << b)];
        count[state]++;
    }
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue