class Solution {
public:
long long wonderfulSubstrings(string word) {
}
};
1915. 最美子字符串的数目
如果某个字符串中 至多一个 字母出现 奇数 次，则称其为 最美 字符串。
"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' 的小写英文字母组成原站题解
python3 解法, 执行用时: 2700 ms, 内存消耗: 17 MB, 提交时间: 2023-06-07 11:11:58
class Solution:
def wonderfulSubstrings(self, word: str) -> int:
cnt = [0] * 1024
cnt[0] = 1 # 初始前缀和为 0，需将其计入出现次数
ans = s = 0
for c in word:
s ^= 1 << (ord(c) - ord('a')) # 计算当前前缀和
ans += cnt[s] # 所有字母均出现偶数次
ans += sum(cnt[s ^ (1 << i)] for i in range(10)) # 枚举其中一个字母出现奇数次，反转该字母的出现次数的奇偶性
cnt[s] += 1 # 更新前缀和出现次数
return ans
java 解法, 执行用时: 21 ms, 内存消耗: 43.4 MB, 提交时间: 2023-06-07 11:11:36
class Solution {
public long wonderfulSubstrings(String word) {
var cnt = new int[1024];
cnt[0] = 1; // 初始前缀和为 0，需将其计入出现次数
var ans = 0L;
for (int i = 0, sum = 0; i < word.length(); ++i) {
sum ^= 1 << (word.charAt(i) - 'a'); // 计算当前前缀和
ans += cnt[sum]; // 所有字母均出现偶数次
for (var j = 1; j < 1024; j <<= 1) // 枚举其中一个字母出现奇数次
ans += cnt[sum ^ j]; // 反转该字母的出现次数的奇偶性
++cnt[sum]; // 更新前缀和出现次数
}
return ans;
}
}
golang 解法, 执行用时: 16 ms, 内存消耗: 6.2 MB, 提交时间: 2023-06-07 11:11:23
func wonderfulSubstrings(word string) (ans int64) {
cnt := [1024]int{1} // 初始前缀和为 0，需将其计入出现次数
sum := 0
for _, c := range word {
sum ^= 1 << (c - 'a') // 计算当前前缀和
ans += int64(cnt[sum]) // 所有字母均出现偶数次
for i := 1; i < 1024; i <<= 1 { // 枚举其中一个字母出现奇数次
ans += int64(cnt[sum^i]) // 反转该字母的出现次数的奇偶性
}
cnt[sum]++ // 更新前缀和出现次数
}
return
}
cpp 解法, 执行用时: 44 ms, 内存消耗: 12.1 MB, 提交时间: 2023-06-07 11:11:08
// 前缀和
class Solution {
public:
long long wonderfulSubstrings(string &word) {
int cnt[1024] = {0};
cnt[0] = 1; // 初始前缀和为 0，需将其计入出现次数
long ans = 0L;
int sum = 0;
for (char c: word) {
sum ^= 1 << (c - 'a'); // 计算当前前缀和
ans += cnt[sum]; // 所有字母均出现偶数次
for (int j = 1; j < 1024; j <<= 1) // 枚举其中一个字母出现奇数次
ans += cnt[sum ^ j]; // 反转该字母的出现次数的奇偶性
++cnt[sum]; // 更新前缀和出现次数
}
return ans;
}
};