Number of Wonderful Substrings
Number of Wonderful Substrings is a medium arrays & hashing problem solved with the prefix sum strategy pattern.
The best approach, optimal (prefix parity masks + counting), runs in O(10 · n) time and O(2^10) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (extend every start) up.
Problem
A string is called wonderful when at most one of its letters appears an odd number of times. For example, "aabbc" is wonderful (only c is odd), while "abc" is not.
You are given word, made only of the first ten lowercase letters 'a' through 'j'. Return how many non-empty substrings of word are wonderful. Substrings at different positions are counted separately, even if they spell the same text.
Examples
Example 1
- Input
word = "abab"- Output
7- Why
- The four single letters, "aba", "bab" (one odd letter each) and "abab" (no odd letters) qualify; "ab" and "ba" have two odd letters.
Example 2
- Input
word = "cdcc"- Output
7- Why
- Four single letters plus "cc", "cdc" and "dcc". The whole string has both c (3) and d (1) odd, so it does not count.
Example 3
- Input
word = "gh"- Output
2- Why
- Only "g" and "h" work; "gh" has two letters with an odd count.
Constraints
1 <= word.length <= 10^5wordcontains only the letters'a'to'j'.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (extend every start) | O(n²) | O(1) |
| Optimal (prefix parity masks + counting) | O(10 · n) | O(2^10) |
1Brute force (extend every start)
O(n²)There are n(n + 1) / 2 substrings and each one is checked in O(1) thanks to the running mask.O(1)Only the mask and loop indices.Fix each start index and extend the end one character at a time, flipping that letter's bit in a running parity mask. The substring is wonderful when the mask has at most one bit set.
- For each start i, set mask = 0.
- For each end j >= i, flip bit word[j] - 'a' in mask.
- If mask & (mask - 1) == 0 (zero or one bit set), add 1 to the answer.
class Solution {
public long wonderfulSubstrings(String word) {
int n = word.length();
long count = 0;
for (int i = 0; i < n; i++) {
int mask = 0;
for (int j = i; j < n; j++) {
mask ^= 1 << (word.charAt(j) - 'a');
if ((mask & (mask - 1)) == 0) count++;
}
}
return count;
}
}class Solution:
def wonderfulSubstrings(self, word: str) -> int:
n = len(word)
count = 0
for i in range(n):
mask = 0
for j in range(i, n):
mask ^= 1 << (ord(word[j]) - 97)
if mask & (mask - 1) == 0:
count += 1
return countclass Solution {
public:
long long wonderfulSubstrings(string word) {
int n = word.size();
long long count = 0;
for (int i = 0; i < n; i++) {
int mask = 0;
for (int j = i; j < n; j++) {
mask ^= 1 << (word[j] - 'a');
if ((mask & (mask - 1)) == 0) count++;
}
}
return count;
}
};function wonderfulSubstrings(word) {
const n = word.length;
let count = 0;
for (let i = 0; i < n; i++) {
let mask = 0;
for (let j = i; j < n; j++) {
mask ^= 1 << (word.charCodeAt(j) - 97);
if ((mask & (mask - 1)) === 0) count++;
}
}
return count;
}2Optimal (prefix parity masks + counting)
O(10 · n)Each character does 11 constant-time lookups.O(2^10)A fixed table of 1024 counters, one per possible parity mask.Let prefix[j] be the parity mask of the first j characters. The substring (i, j] has parity mask prefix[i] ^ prefix[j]. It is wonderful when that XOR is 0 or a single bit, so for every prefix count earlier prefixes with the same mask or a mask that differs in exactly one of the 10 bits. Since there are only 2^10 masks, an array of 1024 counters is enough.
- Create freq[1024] and set freq[0] = 1 for the empty prefix.
- Walk the string, flipping bit c - 'a' in mask for each character c.
- Add freq[mask] (all letters even) and freq[mask ^ (1 << b)] for b in 0..9 (exactly one odd letter).
- Then increment freq[mask].
class Solution {
public long wonderfulSubstrings(String word) {
long[] freq = new long[1 << 10];
freq[0] = 1;
int mask = 0;
long count = 0;
for (int k = 0; k < word.length(); k++) {
mask ^= 1 << (word.charAt(k) - 'a');
count += freq[mask];
for (int b = 0; b < 10; b++) {
count += freq[mask ^ (1 << b)];
}
freq[mask]++;
}
return count;
}
}class Solution:
def wonderfulSubstrings(self, word: str) -> int:
freq = [0] * 1024
freq[0] = 1
mask = 0
count = 0
for ch in word:
mask ^= 1 << (ord(ch) - 97)
count += freq[mask]
for b in range(10):
count += freq[mask ^ (1 << b)]
freq[mask] += 1
return countclass Solution {
public:
long long wonderfulSubstrings(string word) {
vector<long long> freq(1 << 10, 0);
freq[0] = 1;
int mask = 0;
long long count = 0;
for (char c : word) {
mask ^= 1 << (c - 'a');
count += freq[mask];
for (int b = 0; b < 10; b++) {
count += freq[mask ^ (1 << b)];
}
freq[mask]++;
}
return count;
}
};function wonderfulSubstrings(word) {
const freq = new Array(1 << 10).fill(0);
freq[0] = 1;
let mask = 0;
let count = 0;
for (let k = 0; k < word.length; k++) {
mask ^= 1 << (word.charCodeAt(k) - 97);
count += freq[mask];
for (let b = 0; b < 10; b++) {
count += freq[mask ^ (1 << b)];
}
freq[mask]++;
}
return count;
}Edge cases to test
- A single character: the answer is 1
- All characters equal: every substring qualifies, n(n + 1) / 2 of them, which needs a 64-bit result
- Many distinct letters, where most substrings fail
- Substrings with zero odd letters (even length palindromic counts) must be counted too
Hints
Hint 1
Only the parity (odd or even) of each letter's count matters, and there are just 10 letters. How can you store all 10 parities in one integer?
Hint 2
If the parity mask of the prefix ending at j equals the mask of the prefix ending at i, the substring between them has every count even.
Hint 3
A substring with exactly one odd letter corresponds to two prefix masks that differ in exactly one bit. For each prefix, look up the same mask and the 10 masks one bit away.
FAQ
What is the best time complexity for Number of Wonderful Substrings?
Optimal (prefix parity masks + counting) runs in O(10 · n) time and O(2^10) extra space. Each character does 11 constant-time lookups.
Which pattern does Number of Wonderful Substrings use?
It is a arrays & hashing problem that uses the prefix sum strategy pattern. Other problems with the same pattern: Subarray Sum Equals K, Subarray with given XOR, Range Sum Query - Immutable.
Is there a brute force solution for Number of Wonderful Substrings?
Yes. Brute force (extend every start) takes O(n²) time and O(1) space. Fix each start index and extend the end one character at a time, flipping that letter's bit in a running parity mask.
Which edge cases should I test for Number of Wonderful Substrings?
A single character: the answer is 1; All characters equal: every substring qualifies, n(n + 1) / 2 of them, which needs a 64-bit result; Many distinct letters, where most substrings fail; Substrings with zero odd letters (even length palindromic counts) must be counted too.