主題
題目連結(jié)：
題目意譯：
一個(gè)美妙字串為一字串其中最多只有一種字母出現(xiàn)奇數(shù)次。
例如，"ccjjc" 和 "abab" 是美妙的，但 "ab" 則不是。
給定一字串 word 其由前十個(gè)小寫英文字母（'a' 到 'j'）所組成，回傳 word 中非空美妙子字串的數(shù)量。如果同樣的子字串出現(xiàn)多次，則每次出現(xiàn)都算進(jìn)計(jì)數(shù)之內(nèi)。
一個(gè)字串之一子字串為字串中一連串的連續(xù)字元之序列。
限制：
1 ≦ word.length ≦ 10 ^ 5
word 由 'a' 到 'j' 的小寫英文字母組成。
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： word = "aba"
輸出： 4
解釋： 四個(gè)美妙子字串以底線標(biāo)示如下：
- "aba" → "a"
- "aba" → "b"
- "aba" → "a"
- "aba" → "aba"
範(fàn)例 2：
輸入： word = "aabb"
輸出： 9
解釋： 九個(gè)美妙子字串以底線標(biāo)示如下：
- "aabb" → "a"
- "aabb" → "aa"
- "aabb" → "aab"
- "aabb" → "aabb"
- "aabb" → "a"
- "aabb" → "abb"
- "aabb" → "b"
- "aabb" → "bb"
- "aabb" → "b"
範(fàn)例 3：
輸入： word = "he"
輸出： 2
解釋： 兩個(gè)美妙子字串以底線標(biāo)示如下：
- "he" → "h"
- "he" → "e"
解題思維：
本題有一點(diǎn)前綴和（Prefix Sums）的味道。不過，當(dāng)然不是真的前綴「和」。
因?yàn)楸绢}的字母只會(huì)有前十個(gè)，所以我們可以用一個(gè)十位元長(zhǎng)的二進(jìn)位數(shù)字來表示哪些字母目前出現(xiàn)奇數(shù)次。例如 1011000010 ，代表著 'j' 、 'h' 、 'g' 、 'b' 這四種字母出現(xiàn)了奇數(shù)次。而可能的組合只會(huì)有 2 ^ 10 = 1024 種。然後我們定義一陣列 C，其中 C[i] 代表字母狀態(tài) i 的個(gè)數(shù)。
定義一個(gè)如上的十位元長(zhǎng)之二進(jìn)位數(shù)字 nowMask = 0000000000 並將 C[0] 設(shè)為 1（代表一開始什麼字母都沒有），而 nowMask 代表著從 word 開頭到目前位置之字母出現(xiàn)狀態(tài)。接著我們掃過 word 中每個(gè)字母 word[i]：
我們將更新 nowMask 為 nowMask ^ (1 << (word[i] - 'a'))，其中 word[i] - 'a' 代表著 word[i] 於字母表中的序位（'a' 為 0 、 'b' 為 1 、……）、「<<」為位元左移，因此 (1 << x) 等價(jià)於 2 ^ x。而「^」（注意，這前面的 2 ^ x 的「^」代表著冪次）代表著位元運(yùn)算中的互斥或 XOR 運(yùn)算，代表兩位元不同為 1 時(shí)結(jié)果為 1，因此 0 XOR 0 = 0 、 0 XOR 1 = 1 、 1 XOR 0 = 1 、 1 XOR 1 = 0。
因此如果該字母於先前出現(xiàn)奇數(shù)次，則現(xiàn)在為偶數(shù)次；先前為偶數(shù)次，則現(xiàn)在為奇數(shù)次。如此便可以更新 word[i] 這種字母的出現(xiàn)情況。
接著我們查詢 C[nowMask]。如果 C[nowMask] ≠ 0，則代表我們可以從先前那些狀態(tài)所發(fā)生的位置產(chǎn)生出一子字串，其為從發(fā)生位置下一個(gè)字元到目前的位置之子字串。可以看到此時(shí)的子字串中所有字母的出現(xiàn)次數(shù)皆為偶數(shù)。而這樣的子字串有 C[nowMask] 個(gè)。
例如有一字串 "aabb"。當(dāng)我們碰到第二個(gè) 'b' 時(shí)，此時(shí)的 nowMask = 0000000000 。而在先前 nowMask = 0000000000 已出現(xiàn)過兩次（C[nowMask] = 2），一次是 ""（最一開始什麼字母都沒有這時(shí)候）、另一次則是 "aa"。此時(shí)我們可以產(chǎn)生出兩個(gè)子字串 "aabb"（由 "" 其後到第二個(gè) 'b' 為止所產(chǎn)生）和 "bb"（由 "aa" 其後到第二個(gè) 'b' 為止所產(chǎn)生）。
接著我們窮舉 'a' ～ 'j' 所有字母。對(duì)於每個(gè)字母 X，我們?nèi)タ?C[nowMask ^ (1 << (X - 'a'))] 是否不等於 0。因?yàn)?nowMask 與 nowMask ^ (1 << (X - 'a')) 會(huì)恰好差一個(gè)位元。所以如果 C[nowMask ^ (1 << (X - 'a'))] 不為 0 ，則代表我們可以從先前 nowMask ^ (1 << (X - 'a')) 所發(fā)生之位置產(chǎn)生出 C[nowMask ^ (1 << (X - 'a'))] 個(gè)子字串（作法同上）。此時(shí)每個(gè)子字串幾乎所有字母都出現(xiàn)偶數(shù)次，除了目前窮舉之字母 X，其將會(huì)出現(xiàn)奇數(shù)次。
回到上例的 "aabb" 的第二個(gè) 'b' 之時(shí)刻。當(dāng) X = 'a' 時(shí)，nowMask' = nowMask ^ (1 << ('a' - 'a')) = 0000000001。而 C[nowMask'] = 1 （先前發(fā)生於第一個(gè) 'a'），因此我們可以產(chǎn)生出一子字串 "abb"；同樣地當(dāng) X = 'b' 時(shí) nowMask' = 0000000010，而 C[nowMask'] = 1（先前發(fā)生於第一個(gè) 'b'），所以可以產(chǎn)生出子字串 "b"（這邊的 'b' 是第二個(gè) 'b' 而不是第一個(gè)，因?yàn)槲覀兪菑牡谝粋€(gè) 'b' 那個(gè)位置往後到當(dāng)前字元）。
因此對(duì)於每個(gè) word 中的字母 word[i]，以其作為結(jié)尾並且符合題目要求之子字串?dāng)?shù)量為 C[nowMask] + C[nowMask ^ (1 << (X - 'a'))]（'a' ≦ X ≦ 'j'）。統(tǒng)計(jì)完以 word[i] 作結(jié)的子字串後，將 C[nowMask] 加 1 ，以示本位置新發(fā)生了一次 nowMask 之狀態(tài)。
最後將過程中所有 word[i] 所產(chǎn)生的子字串之?dāng)?shù)量加總即為所求。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
