1915. Number of Wonderful Substrings

第一个提示：word consists of lowercase English letters from 'a' to 'j'
另一个提示是我们只关心odd number of frequency.出现次数的奇偶只有两种状态这两个提示指向了使用bit mask:
- 一共10位bit表示a-j 10个字母
- 每个bit有0或1两种状态

给定word[:i+1]的mask1, 如何找到相关的substring? substring的mask2有两种可能性：

substring 没有基数频率的字母 =》mask2 = 0 =〉如果历史记录里存在一个mask3和mask1相等，假设mask3来自于word[:j+1] where j < i, 那么word[j+1:i+1]就应该是wonderful substring因为word[j+1:i+1]对应的mask2 is 0
存在一个prefix (ie, word[:j+1] where j < i) 对应的mask2使得 mask1 ^ mask = t where t只有一个bit是1。t可能的值有 1<<k where k in range (10). mask2 = mask1 ^ t

class Solution:
    def wonderfulSubstrings(self, word: str) -> int:
        freq = Counter()
        freq[0] = 1 #某些prefix可能本身已是wonderful substring. 所以需要记录没有任何字母时的mask
        
        mask = 0
        res = 0
        for i, ch in enumerate(word):            
            mask ^= 1 << (ord(ch) - ord('a')) # toggle 
                
            for j in range(10):
                res += freq[(1 << j) ^ mask] # 找出使得substring对应的mask2变成2的指数次幂的prefix
            res += freq[mask] # 找出使得substring对应的mask2变成0的prefix
            
            freq[mask] += 1
        return res

1915. Number of Wonderful Substrings - cocoder39/coco39_LC GitHub Wiki