1915. Number of Wonderful Substrings

1915. Number of Wonderful Substrings (Medium)

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: 4
Explanation: The four wonderful substrings are underlined below:
- "aba" -> "a"
- "aba" -> "b"
- "aba" -> "a"
- "aba" -> "aba"

Example 2:

Input: word = "aabb"
Output: 9
Explanation: The nine wonderful substrings are underlined below:
- "aabb" -> "a"
- "aabb" -> "aa"
- "aabb" -> "aab"
- "aabb" -> "aabb"
- "aabb" -> "a"
- "aabb" -> "abb"
- "aabb" -> "b"
- "aabb" -> "bb"
- "aabb" -> "b"

Example 3:

Input: word = "he"
Output: 2
Explanation: The two wonderful substrings are underlined below:
- "he" -> "h"
- "he" -> "e"

 

Constraints:

• 1 <= word.length <= 105
• word consists of lowercase English letters from 'a' to 'j'.

Related Topics:
String, Bit Manipulation

Solution 1. Prefix State Map

// OJ: https://leetcode.com/problems/number-of-wonderful-substrings/
// Author: github.com/lzl124631x
// Time: O(NC) where `N` is the length of `s` and `C` is the range of the characters
// Space: O(2^C)
class Solution {
public:
    long long wonderfulSubstrings(string s) {
        int N = s.size(), mask = 0;
        long long ans = 0, m[1024] = {1};
        for (int i = 0; i < N; ++i) {
            mask ^= 1 << (s[i] - 'a');
            ans += m[mask];
            for (int j = 0; j < 10; ++j) {
                int next = mask ^ (1 << j);
                ans += m[next];
            }
            m[mask]++;
        }
        return ans;
    }
};