Number of Wonderful Substrings
A wonderful string is a string where at most one letter appears an odd number of times.
- For example,
"ccjjc"and"abab"are wonderful, but"ab"is not.
Given a string word that consists of the first ten lowercase English letters ('a' through 'j'), return the number of wonderful non-empty substrings in word. If the same substring appears multiple times in word, then count each occurrence separately.
A substring is a contiguous sequence of characters in a string.
Example 1
Input
word = "aba"Output
4The four wonderful substrings are "a", "b", "a", and "aba".
Example 2
Input
word = "aabb"Output
9The nine wonderful substrings are "a", "aa", "aab", "aabb", "a", "abb", "b", "bb", and "b".
Constraints
- 1 <= word.length <= 10^5
- word consists of lowercase English letters from 'a' to 'j'.