Number of Wonderful Substrings
Asked at Uber
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Uber | MEDIUM | View all Uber questions → |
How to Think About It
Brute force: check every substring, count odd-frequency letters — O(n^2 * 26)
Represent letter parity as a bitmask where bit i = 1 means letter i has odd count
Use prefix XOR: prefix[j] XOR prefix[i] gives parity of substring [i, j)
A substring is wonderful if the XOR result has at most one bit set
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.
What Trips People Up in Real Interviews
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
Solution Code
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 resultFrequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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