Count substrings where at most one character appears an odd number of times.
Wonderful Substrings
gfgProblem
You are given a string word consisting of lowercase English letters from a to j.
A substring is called wonderful if at most one letter appears an odd number of times in that substring.
Return the number of wonderful substrings in word.
A substring is a contiguous non-empty sequence of characters.
Key idea to notice
Since there are only 10 possible letters, it is often useful to track the parity (even/odd) of each letter count using a bitmask.
Input Format
- A single string
word. wordcontains only lowercase letters fromatoj.
Output Format
- Return an integer: the number of wonderful substrings.
Constraints
1 <= word.length <= $10^{5}$word[i]is one of'a'through'j'
Example 1
Input
word = "aba"
Output
4
Explanation
The wonderful substrings are "a" (at index 0), "b", "a" (at index 2), and "aba".
Example 2
Input
word = "aabb"
Output
9
Explanation
Every substring is wonderful except "ab" and "ba". The total number of substrings is 10, so the answer is 9.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.