1915. 最美子字符串的数目

English Version

题目描述

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

• 例如，"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' 的小写英文字母组成

解法

状态压缩 + 前缀和

Python3

Java

JavaScript

/**
 * @param {string} word
 * @return {number}
 */
var wonderfulSubstrings = function(word) {
    let n = 1 << 10;
    let counts = new Array(n).fill(0);
    counts[0] = 1;
    let pre = 0;
    let ans = 0;
    for (let c of word) {
        let cur = c.charCodeAt(0) - 'a'.charCodeAt(0);
        pre ^= (1 << cur);
        ans += counts[pre];
        for (let i = 1; i < n; i <<= 1) {
            ans += counts[pre ^ i];
        }
        ++counts[pre];
    }
    return ans;
};

...