5799. 最美子字符串的数目

# 题目

## 5799. 最美子字符串的数目

[https://leetcode-cn.com/problems/number-of-wonderful-substrings/](https://leetcode-cn.com/problems/number-of-wonderful-substrings/)

如果某个字符串中 **至多一个** 字母出现 **奇数** 次，则称其为 **最美** 字符串。

- 例如，`"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 <= 105`
- `word` 由从 `'a'` 到 `'j'` 的小写英文字母组成

# 题解

## 思路

前缀和，将「字母出现次数」转换成「字母出现次数的奇偶性」，这可以用一个长为 10 的二进制串表示，二进制串的第 i 位为 0 表示第 i 个小写字母出现了偶数次，为 1 表示第 i 个小写字母出现了奇数次

## 代码

```javascript
/**
 * @param {string} word
 * @return {number}
 */
// 前缀和 位运算
var wonderfulSubstrings = function(word) {
    // 统计数组
    let cnt = new Array(1024).fill(0);
    // 结果
    let ans = 0;
    let pre = 0;
    // 初始化数据
    cnt[0] = 1;
    for(let str of word){
        // 前缀和，和上一个进行异或
        pre ^= 1 << (str.charCodeAt() - 'a'.charCodeAt());
        // 加上结果值，如果是0，表示所有字母出现偶数次
        ans += cnt[pre];
        // 计算0-9位置上只出现1次的值
        for(let i = 0; i < 10;i++){
            ans += cnt[pre ^ 1 << i];
        }
        // 当前的前缀和在下次计算时需要加1
        cnt[pre]++;
    }
    return ans;
};
```