我要吐了，狗屎題目
想了好久，難怪我上不了姑姑魯
1915. Number of Wonderful Substrings
有一個字串由'a'~'j'組成
請回傳wonderful substring的數量
如果該字串裡只有一個字元的數量是奇數那就是wonderful substring
思路:
有10種字元，而且只要紀錄字元數量是奇數還是偶數
那就用10個bit分別去紀錄，'a'是第0個字元以此類推
XOR 1<<(s[i]-'a')
並且用hashmap去紀錄到目前為止出現過的組合
如何找符合條件的子字串?
假設index 0~i的字元組合為 111000110
那就要去找到index i之前有沒有出現過一樣的組合
或是跟該字元組合剛好差1個bit : 111000110 XOR 011000110 = 1000000000
這樣就能找出來了
GOLANG CODE:
func wonderfulSubstrings(word string) int64 {
table:=[1024]int{}
table[0]=1 //字元組合剛好全部是偶數
val:=0
res:=0
for i:=0;i<len(word);i++{
val^= (1<<(word[i]-'a'))
res+=table[val]
for j:=0;j<10;j++{
idx:= val ^ (1<<j)
res+=table[idx]
}
table[val]++
}
return int64(res)
}