1915-最美子字符串的数目

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 17:01:06 2023-09-13 17:01:06 Updated    

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

  • 例如，"ccjjc" 和 "abab" 都是最美字符串，但 "ab" 不是。

给你一个字符串 word ，该字符串由前十个小写英文字母组成（'a' 到 'j'）。请你返回 word 中 最美非空子字符串 的数目
。 如果同样的子字符串在 __word 中出现多次，那么应当对 每次出现 分别计数 。

子字符串 是字符串中的一个连续字符序列。

示例 1：

**输入：** word = "aba"
**输出：** 4
**解释：** 4 个最美子字符串如下所示：
- " **a** ba" -> "a"
- "a **b** a" -> "b"
- "ab **a** " -> "a"
- " **aba** " -> "aba"

示例 2：

**输入：** word = "aabb"
**输出：** 9
**解释：** 9 个最美子字符串如下所示：
- " **a** abb" -> "a"
- " **aa** bb" -> "aa"
- " **aab** b" -> "aab"
- " **aabb** " -> "aabb"
- "a **a** bb" -> "a"
- "a **abb** " -> "abb"
- "aa **b** b" -> "b"
- "aa **bb** " -> "bb"
- "aab **b** " -> "b"

示例 3：

**输入：** word = "he"
**输出：** 2
**解释：** 2 个最美子字符串如下所示：
- " **h** e" -> "h"
- "h **e** " -> "e"

提示：

  • 1 <= word.length <= 105
  • word 由从 'a' 到 'j' 的小写英文字母组成

方法一：状态压缩

提示 1

如果字符串 word 的某个子串 word}[i..j] 是最美字符串，那么其中最多只有一个字符出现奇数次，这说明：

对于任意一次字符 c 而言，word 的 i-1 前缀 word}[0..i-1] 与 j 前缀 word}[0..j] 中字符 c 的出现次数必须同奇偶。同时，我们最多允许有一个字符 c，它在两个前缀中出现次数的奇偶性不同。

提示 2

由于题目保证了 word 中只会包含前 10 个小写字母，因此我们可以用一个长度为 10 的二进制数 mask 表示 word 的前缀中 [\text{a}, \text{j}] 出现次数的奇偶性，其中 mask 的第 i 位为 1 表示第 i 个字母出现了奇数次，0 表示第 i 个字母出现了偶数次。

记 word 的 k 前缀 word}[0..k] 对应的二进制数为 mask}k。根据提示 1，word}[i..j] 是最美字符串，当且仅当 mask}{i-1 和 mask}_j 的二进制表示最多只有一位不同。

特别地，如果 i=0，那么 mask}_{-1} = 0，即所有字母均未出现过。

思路与算法

我们对字符串 word 进行一次遍历。

当我们遍历到 word}[i] 时，我们首先计算出 mask}_i，再遍历 mask}_i 的 10 个二进制位，将其翻转（从 0 变为 1 或者从 1 变为 0）得到 mask}’_i。此时 mask}_i 和 mask}’_i 的二进制表示恰好有一位不同。

为了快速计算答案，我们需要使用一个哈希映射 freq 存储每一个 mask 出现的次数。这样一来，我们直接将答案增加 freq}[\textit{mask}’_i] 即可。此外，我们还需要将答案增加 freq}[\textit{mask}_i]，即两个前缀出现字母的奇偶性完全相同。

细节

在开始遍历前，我们需要将 mask}_{-1 放入哈希映射中。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    long long wonderfulSubstrings(string word) {
        unordered_map<int, int> freq = { {0, 1} };
        int mask = 0;
        long long ans = 0;
        for (char ch: word) {
            int idx = ch - 'a';
            mask ^= (1 << idx);
            if (freq.count(mask)) {
                ans += freq[mask];
            }
            for (int i = 0; i < 10; ++i) {
                if (int mask_pre = mask ^ (1 << i); freq.count(mask_pre)) {
                    ans += freq[mask_pre];
                }
            }
            ++freq[mask];
        }
        return ans;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def wonderfulSubstrings(self, word: str) -> int:
        freq = Counter([0])
        mask, ans = 0, 0
        
        for ch in word:
            idx = ord(ch) - ord("a")
            mask ^= (1 << idx)
            if mask in freq:
                ans += freq[mask]
            for i in range(10):
                mask_pre = mask ^ (1 << i)
                if (mask_pre := mask ^ (1 << i)) in freq:
                    ans += freq[mask_pre]
            freq[mask] += 1
        
        return ans

复杂度分析

  • 时间复杂度：O(n|\Sigma|)，其中 n 是字符串 word 的长度，\Sigma 是字符集，在本题中 |\Sigma|=10。

  • 空间复杂度：O(\min(n, 2^{|\Sigma|}))。哈希映射中存储的键值对个数由字符串 word 的长度 n 以及 |\Sigma| 位二进制数的总数 2^{|\Sigma| 共同限制，因此空间复杂度为 O(\min(n, 2^{|\Sigma|}))。

 Comments
On this page
1915-最美子字符串的数目