我要吐了，狗屎题目
想了好久，难怪我上不了姑姑鲁
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)
}