最美子字符串的数目

这个题解使用了位运算和前缀XOR的概念来高效地解决问题。首先，每个字母可以映射到一个10位的二进制数中的某一位（因为字母'a'到'j'共有10个）。对于字符串中的每个字符，通过一个异或操作更新当前的前缀XOR值。这个前缀XOR在二进制表示中，每位的1表示对应位置的字母出现奇数次。题解中使用了一个字典来存储每个前缀XOR出现的次数。然后，计算所有可能的最美子字符串的数量。只要当前的前缀XOR或者与之前某个前缀XOR的差异正好是一位（即异或结果中只有一个位是1），则表示这之间的子字符串是最美的。总体上，此方法避免了直接检查每个子字符串，而是通过巧妙地利用前缀XOR来统计满足条件的子字符串数量。

时间复杂度: O(n + K^2)，其中K是唯一前缀XOR值的数量，最坏情况下K为1024

空间复杂度: O(K)，其中K为前缀XOR的不同值的数量，最坏情况下为1024

class Solution:
    def wonderfulSubstrings(self, word: str) -> int:
        @cache
        def two(s):
            return 1 << ord(s) - ord('a')
        res = 0
        a = {}
        a[res] = 1
        for w in word:
            res ^= two(w)
            if res in a:
                a[res] += 1
            else:
                a[res] = 1
        ans = 0
        l = list(a.keys())
        for x in l:
            ans += a[x]*(a[x]-1) // 2
        
        n = len(l)
        for i in range(n-1):
            for j in range(i+1,n):
                if (l[i] ^ l[j]).bit_count() == 1:
                    ans += a[l[i]]*a[l[j]]
        return ans