Number of Wonderful Substrings

Medium
741.

Number of Wonderful Substrings

Number of Wonderful Substrings is a medium coding problem on strings, hash table and bit manipulation, asked in Amazon, Google and Meta interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} word
 * @return {number}
 */
var wonderfulSubstrings = function(word) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Wonderful Substrings — Problem & Solution

Number of Wonderful Substrings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Number of Wonderful Substrings is a medium coding problem on strings, hash table and bit manipulation, asked in Amazon, Google and Meta interviews.

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.

Hints for Number of Wonderful Substrings

  1. Hint 1

    Only the parity of each letter matters, and there are ten letters — so the state is a 10-bit mask.

  2. Hint 2

    A substring is wonderful when the XOR of the two end states has at most one set bit.

  3. Hint 3

    Tally how often each of the 1024 states has occurred, then for each prefix add the tally of the same state plus the tallies of the ten states one bit away.

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

  1. Keep count[1024], seeded with count[0] = 1 for the empty prefix.
  2. Sweep the string, toggling the bit of each letter into state.
  3. Add count[state] (zero odd letters) and count[state ^ (1 << b)] for each of the ten bits (exactly one odd letter).
  4. 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

Java

public static int wonderfulSubstrings(String word) {
    int[] count = new int[1024];
    count[0] = 1;
    int state = 0;
    long total = 0;
    for (int i = 0; i < word.length(); i++) {
        state ^= 1 << (word.charAt(i) - 'a');
        total += count[state];
        for (int b = 0; b < 10; b++) total += count[state ^ (1 << b)];
        count[state]++;
    }
    return (int) total;
}

C++

int wonderfulSubstrings(string word) {
    vector<int> count(1024, 0);
    count[0] = 1;
    int state = 0;
    long long total = 0;
    for (char c : word) {
        state ^= 1 << (c - 'a');
        total += count[state];
        for (int b = 0; b < 10; b++) total += count[state ^ (1 << b)];
        count[state]++;
    }
    return (int) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets