原文链接: https://leetcode-cn.com/problems/number-of-wonderful-substrings
英文原文
A wonderful string is a string where at most one letter appears an odd number of times.
- For example,
"ccjjc"and"abab"are wonderful, but"ab"is not.
Given a string word that consists of the first ten lowercase English letters ('a' through 'j'), return the number of wonderful non-empty substrings in word. If the same substring appears multiple times in word, then count each occurrence separately.
A substring is a contiguous sequence of characters in a string.
Example 1:
Input: word = "aba" Output: 4 Explanation: The four wonderful substrings are underlined below: - "aba" -> "a" - "aba" -> "b" - "aba" -> "a" - "aba" -> "aba"
Example 2:
Input: word = "aabb" Output: 9 Explanation: The nine wonderful substrings are underlined below: - "aabb" -> "a" - "aabb" -> "aa" - "aabb" -> "aab" - "aabb" -> "aabb" - "aabb" -> "a" - "aabb" -> "abb" - "aabb" -> "b" - "aabb" -> "bb" - "aabb" -> "b"
Example 3:
Input: word = "he" Output: 2 Explanation: The two wonderful substrings are underlined below: - "he" -> "h" - "he" -> "e"
Constraints:
1 <= word.length <= 105wordconsists of lowercase English letters from'a'to'j'.
中文题目
如果某个字符串中 至多一个 字母出现 奇数 次，则称其为 最美 字符串。
- 例如，
"ccjjc"和"abab"都是最美字符串，但"ab"不是。
给你一个字符串 word ，该字符串由前十个小写英文字母组成（'a' 到 'j'）。请你返回 word 中 最美非空子字符串 的数目。如果同样的子字符串在 word 中出现多次，那么应当对 每次出现 分别计数。
子字符串 是字符串中的一个连续字符序列。
示例 1：
输入：word = "aba" 输出：4 解释：4 个最美子字符串如下所示： - "aba" -> "a" - "aba" -> "b" - "aba" -> "a" - "aba" -> "aba"
示例 2：
输入：word = "aabb" 输出：9 解释：9 个最美子字符串如下所示： - "aabb" -> "a" - "aabb" -> "aa" - "aabb" -> "aab" - "aabb" -> "aabb" - "aabb" -> "a" - "aabb" -> "abb" - "aabb" -> "b" - "aabb" -> "bb" - "aabb" -> "b"
示例 3：
输入：word = "he" 输出：2 解释：2 个最美子字符串如下所示： - "he" -> "h" - "he" -> "e"
提示：
1 <= word.length <= 105word由从'a'到'j'的小写英文字母组成
通过代码
高赞题解
由于我们只关心每个字母出现次数的奇偶性，因此可以将「字母出现次数」转换成「字母出现次数的奇偶性」，这可以用一个长为 $10$ 的二进制串表示，二进制串的第 $i$ 位为 $0$ 表示第 $i$ 个小写字母出现了偶数次，为 $1$ 表示第 $i$ 个小写字母出现了奇数次。
考虑字母出现次数的前缀和，由于只考虑奇偶性，我们也可以将其视作一个长为 $10$ 的二进制串。此时计算前缀和由加法运算改为异或运算，这是因为异或运算的本质是在模 $2$ 剩余系中进行加法运算，刚好对应奇偶性的变化。
若有两个不同下标的前缀和相同，则这两个前缀和的异或结果为 $0$，意味着这段子串的各个字母的个数均为偶数，符合题目要求。因此，我们可以在求前缀和的同时，用一个长为 $2^{10}=1024$ 的 $\textit{cnt}$ 数组统计每个前缀和二进制串出现的次数，从而得到相同前缀和的对数，即各个字母的个数均为偶数的子串个数。
题目还允许有一个字母出现奇数次，这需要我们寻找两个前缀和，其异或结果的二进制数中恰好有一个 $1$，意味着这段子串的各个字母的个数仅有一个为奇数。对此我们可以枚举当前前缀和的每个比特，将其反转，然后去 $\textit{cnt}$ 中查找该前缀和的出现次数。
将所有统计到的次数累加即为答案。时间复杂度为 $O(10\cdot n)$，$n$ 为字符串 $\textit{word}$ 的长度。
上面所说的技巧在前缀和的题目中经常用到，例如：
- 560. 和为 K 的子数组
- 930. 和相同的二元子数组
- 974. 和可被 K 整除的子数组
- 1371. 每个元音包含偶数次的最长子字符串
- 1542. 找出最长的超赞子字符串
- 1590. 使数组和能被 P 整除
func wonderfulSubstrings(word string) int64 {
cnt := [1024]int{1} // 初始前缀和为 0，需将其计入出现次数
ans, pre := 0, 0
for _, ch := range word {
pre ^= 1 << (ch - 'a') // 计算当前前缀和
ans += cnt[pre] // 所有字母均出现偶数次
for i := 1; i < 1024; i <<= 1 { // 枚举其中一个字母出现奇数次
ans += cnt[pre^i] // 反转第 i 个字母的出现次数的奇偶性
}
cnt[pre]++ // 更新前缀和出现次数
}
return int64(ans)
}统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 2999 | 7595 | 39.5% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
