MediumHash TableStringBit ManipulationPrefix SumUpdated Sep 2026

1915. Number of Wonderful Substrings

Asked at Uber

Difficulty

Medium

Time

O(n * 10)

Space

O(2^10)

Pattern

Hash Table

Companies

1

Problem

You are given a string word made only of the first ten lowercase letters, 'a' through 'j'. A string is called wonderful when at most one of its letters appears an odd number of times. All other letters must appear an even number of times (zero counts as even).

Return the number of non-empty substrings of word that are wonderful. A substring is a block of characters that sit next to each other in word. If the same block of characters appears in more than one place, count each place separately.

For example, in "aba" the wonderful substrings are the two single "a" blocks, the single "b", and the whole string "aba". That is 4.

Which substrings are wonderful?

word"aba"aba012"aba": a appears twice (even), b once (odd) —wonderfulword"ab"aba012"ab": a once, b once — two odd letters, not wonderful
A block counts when at most one of its letters has an odd count.

Constraints

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

Examples

Example 1
Inputword = "aba"
Output4
WhyThe single letters "a", "b", "a" each have one odd letter. The whole string "aba" has a twice (even) and b once (odd), so it also qualifies. "ab" and "ba" have two odd letters, so they do not count. Total 4.
Example 2
Inputword = "aabb"
Output9
WhyAll four single letters count. The pairs "aa" and "bb" count. The triples "aab" and "abb" count. The whole string "aabb" counts. That is 4 + 2 + 2 + 1 = 9.
Example 3
Inputword = "he"
Output2
WhyEach letter appears once, so each single letter is wonderful. The whole string "he" has two odd letters, so it is not wonderful. Total 2.

Asked At

1 companies
CompanyDifficulty
UberMediumView all Uber questions →

How to Think About It

1

Brute force: check every substring, count odd-frequency letters — O(n^2 * 26)

2

Represent letter parity as a bitmask where bit i = 1 means letter i has odd count

3

Use prefix XOR: prefix[j] XOR prefix[i] gives parity of substring [i, j)

4

A substring is wonderful if the XOR result has at most one bit set

5

Count occurrences of each prefix mask, use hashmap, for each mask check mask, mask^(1<<k)

Optimal Approach

Use a bitmask to track parity of each letter. Build prefix XOR where each bit represents odd/even count of that letter. A substring [i,j] is wonderful if prefix[j] XOR prefix[i] has at most one set bit. Use a hashmap to count prefix mask occurrences. For each mask, add counts of the same mask and all masks that differ by exactly one bit. This gives O(n * 26) time.

Prefix parity masks

prefix masks0aabb0123mask[i] = parity of word[0..i-1]; mask[0] = 0 meansall evenprefix masksXOR = a0aabb0123mask[2] XOR mask[3] = "a" — one bit set, so "ba" iswonderfulsubstring [i,j) is wonderfuliff mask[j] XOR mask[i] has ≤ 1 set bitso count mask[j] and mask[j] ^ (1<<k)
The parity of a substring is the XOR of two prefix masks, so we just count matching masks.
ComplexityTime O(n * 10)Space O(2^10)We scan the string once, and for each character we look at 11 mask values (the mask itself plus 10 one-bit flips); the hashmap holds at most 1024 masks.

What Trips People Up in Real Interviews

1

Clarify: single character substrings are always wonderful

2

Bit manipulation insight: number with at most one set bit = 0 or power of 2

3

prefix XOR stores parity of counts up to current position

4

Initialize count map with {0: 1} for empty prefix

5

For each position, add counts of masks that differ by at most one bit

Solution Code

O(n * 10) time
class Solution:
    def wonderfulSubstrings(self, word: str) -> int:
        from collections import Counter
        count = Counter()
        count[0] = 1
        mask = 0
        result = 0
        for ch in word:
            mask ^= 1 << (ord(ch) - ord('a'))
            result += count[mask]
            for k in range(10):
                result += count[mask ^ (1 << k)]
            count[mask] += 1
        return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Number of Wonderful Substrings problem?

A wonderful string is one where at most one letter appears an odd number of times. Given a string word consisting of lowercase English letters, return the number of wonderful non-empty substrings. A substring is a contiguous sequence of characters within the string.

How do you solve Number of Wonderful Substrings?

The optimal approach runs in O(n * 10) time and O(2^10) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Number of Wonderful Substrings?

Number of Wonderful Substrings is asked at Uber. It is a medium difficulty problem.

What are common mistakes on Number of Wonderful Substrings?
  • Clarify: single character substrings are always wonderful
  • Bit manipulation insight: number with at most one set bit = 0 or power of 2
  • prefix XOR stores parity of counts up to current position
  • Initialize count map with {0: 1} for empty prefix
  • For each position, add counts of masks that differ by at most one bit