https://leetcode.com/problems/number-of-wonderful-substrings/description
1915. Number of Wonderful Substrings
给你一个包含小写字母a~j的字串，如果一个子字串的所有字母只有一个字母出现奇数次
那么他就是一个超赞字串，求出s里面有几个超赞子字串。
思路：
1.我们要判断一个字串是不是超赞字串要检查他的奇偶，我们可以用一个二进制数字表
示，奇数为1偶数为0，因为有10个 字母所以需要10位数的二进制就可以表示，状
态初始化为0000000000 -> i = -1 (什么都不加必定是偶数)
假设加入一个a状态变成1000000000 -> i = 0
加入一个b状态变成1100000000 -> i = 1
加入一个a状态变成0100000000 -> i = 2
加入一个b状态变成0000000000 -> i = 3
...
为了方便讨论，后面我们称二进制数字为"状态"
2.如果 i 不同但是状态相同(例如上面i=-1和i=3)，两个"状态"之间的字母必定只会出
现偶数次(奇数不可能相同)，所以：
b ... [xxxxx] ... b
如果最后一个b的状态等于前面的那个b，可以不断地扩展会变成：
b -> [中间必定是偶数] -> b -> [中间必定是偶数] -> b
因为这个特性，只要当前的状态前面出现过，他就可以跟前面的状态接在一起变成一
个新的超赞数字，就像是
b => bb => bbb
这样所以我们只要找有几个b就好，找的过程又可以分成奇偶两个case。
3.可以使用前缀和技巧求解，因为最多有2^10个状态所以可以把map换成array
假定 cnt[x] 表示二进制x这个状态的出现次数:
(1) 任何数加上偶数，奇偶性不变。
同第二点所述，累加前面的 cnt[x] 总数(只要该状态有出现过就一定可以累加)
(2) 任何数加上奇数，奇数变偶数，偶数变奇数。
假设前面存在一个前缀字串 x 可和 word[i] 组成一个超赞字串，那么必定满足:
x ^ word[i] = 只有一个一的二进制数
而该数x刚好会等于 word[i] 的状态每个位数翻转1，假定 word[i]=0000000010
0000000011 ^ 0000000010 = 0000000001
0000000000 ^ 0000000010 = 0000000010
0000000110 ^ 0000000010 = 0000000100
0000001010 ^ 0000000010 = 0000001000
0000010010 ^ 0000000010 = 0000010000
0000100010 ^ 0000000010 = 0000100000
0001000010 ^ 0000000010 = 0001000000
0010000010 ^ 0000000010 = 0010000000
0100000010 ^ 0000000010 = 0100000000
1000000010 ^ 0000000010 = 1000000000
所以我们去找前面所有 word[i] 翻转一个位元的状态共有几个，全部累加起来就好。
pycode:

大师：0

:O

我这题看解答 狗干南y

:O

大师