最美子字符串的数目
1.题目简述
如果某个字符串中至多一个字母出现奇数次，则称其为最美字符串。
例如，"ccjjc" 和 "abab" 都是最美字符串，但 "ab" 不是。给你一个字符串 word ，该字符串由前十个小写英文字母组成（'a' 到 'j'）。请你返回 word 中 最美非空子字符串 的数目。如果同样的子字符串在 word中出现多次，那么应当对每次出现分别计数。
子字符串是字符串中的一个连续字符序列。
数据范围：
1 <= word.size() <=
word由从 'a' 到 'j' 的小写英文字母组成；
（力扣原题链接：https://leetcode-cn.com/problems/number-of-wonderful-substrings）
示例1：
输入：word = "aba"
输出：4
解释：4 个最美子字符串如下所示：
"aba" -> "a"
"aba" -> "b"
"aba" -> "a"
"aba" -> "aba"
2.简单分析
首先，看题意我们可以知道暴力算法应该是分别遍历两个下标，然后判断该下标之间的子字符串是否是最美字符串。然而这种算法复杂度是，在该题的数据范围内肯定过不去。因此自然而然想到用前缀和来优化，即首先预处理出各个下标的每个字符的数量，在进行子字符串判断时就可以以
是复杂度进行判断，因此前缀和技巧优化后的时间复杂度是
。但是，显然在
的数据范围下，
的时间复杂度仍然会超时。
一般来说，要针对前缀和更进一步优化都是采用hash预处理， 此外，注意到word只由 'a' 到 'j' 的小写字母组成，因此可以考虑采用二进制状态表示该下标处字母个数的奇偶性，即 st & (1 << (c - 'a')) == 1 表示字母 c 的前缀和为奇数个，否则为偶数个。综上所述，hash 保存 word中直到下标 index 处，前面各种奇偶性状态的数量。因为只有11种符合条件的情况(只有单个字母为奇数+所有字母都为偶数)，那么最后的时间复杂度为。
3.代码示例
long long wonderfulSubstrings(string word) {
unordered_map<int,int> presum;
presum[0]=1;
int n = word.size(), res = 0;
long long ans = 0;
for(int i=0; i<n; ++i){
res ^= (1<<(word[i]-'a')); //加上当前字母，其奇偶性状态
for(int j = 0; j<10; ++j){
int key = res^(1<<j);
ans += presum[key]; //只有单个字母为技术的情况
}
ans += presum[res]; //所有字母都为偶数的情况
presum[res]++; //到下标i为止，记录状态为res的小标数量
}
return ans;
}
