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.
- 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 <= 1000word consists of letters from a to j.
Hints for Number of Wonderful Substrings
Hint 1
Only the parity of each letter matters, and there are ten letters — so the state is a 10-bit mask.
Hint 2
A substring is wonderful when the XOR of the two end states has at most one set bit.
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
- Keep
count[1024], seeded withcount[0] = 1for the empty prefix. - Sweep the string, toggling the bit of each letter into
state. - Add
count[state](zero odd letters) andcount[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] = 1seed 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 totalJava
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