最美子字符串的數(shù)目
1.題目簡述
??如果某個(gè)字符串中至多一個(gè)字母出現(xiàn)奇數(shù)次钝计，則稱其為最美字符串坡慌。
例如蠢笋，"ccjjc" 和 "abab" 都是最美字符串雇卷，但 "ab" 不是。給你一個(gè)字符串 word 鲸睛，該字符串由前十個(gè)小寫英文字母組成（'a' 到 'j'）娜饵。請你返回 word 中 最美非空子字符串 的數(shù)目。如果同樣的子字符串在 word中出現(xiàn)多次官辈，那么應(yīng)當(dāng)對每次出現(xiàn)分別計(jì)數(shù)箱舞。
子字符串是字符串中的一個(gè)連續(xù)字符序列。
數(shù)據(jù)范圍：
1 <= word.size() <=
word由從 'a' 到 'j' 的小寫英文字母組成拳亿；
（力扣原題鏈接：https://leetcode-cn.com/problems/number-of-wonderful-substrings）
示例1：
輸入：word = "aba"
輸出：4
解釋：4 個(gè)最美子字符串如下所示：
"aba" -> "a"
"aba" -> "b"
"aba" -> "a"
"aba" -> "aba"
2.簡單分析
??首先晴股，看題意我們可以知道暴力算法應(yīng)該是分別遍歷兩個(gè)下標(biāo)，然后判斷該下標(biāo)之間的子字符串是否是最美字符串肺魁。然而這種算法復(fù)雜度是电湘，在該題的數(shù)據(jù)范圍內(nèi)肯定過不去。因此自然而然想到用前綴和來優(yōu)化万搔，即首先預(yù)處理出各個(gè)下標(biāo)的每個(gè)字符的數(shù)量胡桨，在進(jìn)行子字符串判斷時(shí)就可以以
是復(fù)雜度進(jìn)行判斷，因此前綴和技巧優(yōu)化后的時(shí)間復(fù)雜度是
瞬雹。但是昧谊，顯然在
的數(shù)據(jù)范圍下，
的時(shí)間復(fù)雜度仍然會(huì)超時(shí)酗捌。
??一般來說呢诬，要針對前綴和更進(jìn)一步優(yōu)化都是采用hash預(yù)處理， 此外胖缤，注意到word只由 'a' 到 'j' 的小寫字母組成尚镰，因此可以考慮采用二進(jìn)制狀態(tài)表示該下標(biāo)處字母個(gè)數(shù)的奇偶性，即 st & (1 << (c - 'a')) == 1 表示字母 c 的前綴和為奇數(shù)個(gè)哪廓，否則為偶數(shù)個(gè)狗唉。綜上所述，hash 保存 word中直到下標(biāo) index 處涡真，前面各種奇偶性狀態(tài)的數(shù)量分俯。因?yàn)橹挥?1種符合條件的情況(只有單個(gè)字母為奇數(shù)+所有字母都為偶數(shù))，那么最后的時(shí)間復(fù)雜度為哆料。
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')); //加上當(dāng)前字母缸剪，其奇偶性狀態(tài)
for(int j = 0; j<10; ++j){
int key = res^(1<<j);
ans += presum[key]; //只有單個(gè)字母為技術(shù)的情況
}
ans += presum[res]; //所有字母都為偶數(shù)的情況
presum[res]++; //到下標(biāo)i為止，記錄狀態(tài)為res的小標(biāo)數(shù)量
}
return ans;
}
