Leetcode 1915. Number of Wonderful Substrings

[Woodyiiiiiii]

看到数组长度和有关substring，首先想到要用到O(n)时间复杂度，无关排序/堆之类的了。

那么选择就有滑动窗口、前缀和、动态规划、01背包等等解决方法，通过提前存储内容来解决重复问题(DP核心)。

一时想不出来，说明还没吃透题意。题目要求最多有一个出现奇数次数的数，同时也限定了数的范围，非常小。显然后者是告诉我们要用固定长度的数组缓存。

继续观察，问题核心变成了奇偶出现次数，那么我们可以简化成01出现，进而可以用状态压缩表明了所有可能出现的状态。用1<<10表示，同时满足题意的状态只能是0和只有1个1的数(比如100...)。如此一来，列举所有目标状态，然后用异或运算来计算状态转换。

class Solution {
    public long wonderfulSubstrings(String word) {
        int[] cnt = new int[1 << 10];
        cnt[0] = 1;
        int mask = 0;
        long ans = 0;
        for (char c : word.toCharArray()) {
            mask ^= 1 << (c - 'a');
            // 0
            ans += cnt[mask];
            for (int b = 0; b < 10; ++b) {
                // 1
                ans += cnt[mask ^ (1 << b)];
            }
            ++cnt[mask];
        }
        return ans;
    }
}

func wonderfulSubstrings(word string) int64 {
    mask := 0
	count := make([]int, 1 <<10)
	count[0] = 1
	var ans int64
	for _, v := range word {
		mask ^= 1 << (v - 'a')
		ans += int64(count[mask])
		for i := 0; i < 10; i++ {
			ans += int64(count[mask ^ (1 << i)])
		}
		count[mask]++
	}
	return ans
}

---

• 1915. Number of Wonderful Substrings