What is the optimal approach to solve the 'Number of Wonderful Substrings' problem?

The optimal solution uses a bitmask to represent the frequency of characters in the string and a hash table to track the number of times each bitmask has appeared.

How do you represent character frequencies for this problem?

Character frequencies are represented as a bitmask, where each bit corresponds to whether a character has appeared an odd or even number of times.

What is a wonderful substring in the context of this problem?

A wonderful substring is one where at most one character has an odd frequency of appearance.

What data structures are most useful for solving this problem?

Hash tables for tracking bitmask frequencies and bit manipulation for efficient frequency state representation are key data structures for this problem.

How can GhostInterview help with bitmask and hash table problems?

GhostInterview provides focused practice on problems involving bitmasking and hash tables, offering strategies for handling complex string and frequency-based challenges.

#1915

Medium

auto_awesome前缀和

LeetCode 题解工作台

最美子字符串的数目

如果某个字符串中至多一个字母出现奇数次，则称其为最美字符串。例如， "ccjjc" 和 "abab" 都是最美字符串，但 "ab" 不是。给你一个字符串 word ，该字符串由前十个小写英文字母组成（ 'a' 到 'j' ）。请你返回 word 中最美非空子字符串的数目。如果…

哈希表字符串位运算前缀和

题目描述

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

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

lightbulb

解题思路

方法一：前缀异或 + 计数

由于字符串中只包含 $10$ 个小写字母，因此可以用一个长度为 $10$ 的二进制数表示字符串中每个字母的奇偶性，其中第 $i$ 位为 $1$ 表示第 $i$ 个字母出现了奇数次，为 $0$ 表示第 $i$ 个字母出现了偶数次。

我们遍历字符串的每个字符，用一个变量 $st$ 维护当前字符串的前缀异或值，用一个数组 $cnt$ 维护每个前缀异或值出现的次数，初始时 $st = 0$ , $cnt[0] = 1$ 。

对于当前遍历到的字符，我们更新其前缀异或值。如果当前的前缀异或值出现了 $cnt[st]$ 次，也就意味着有 $cnt[st]$ 个子字符串满足所有字母的出现次数均为偶数，因此我们将答案增加 $cnt[st]$ 。此外，对于 $0 \le i < 10$ ，如果当前的前缀异或值 $st$ 的第 $i$ 位为 $1$ ，那么我们还可以找到一个字母出现了奇数次，我们将答案增加 $cnt[st \oplus (1 << i)]$ 。最后，我们将 $st$ 出现的次数增加 $1$ 。继续遍历下一个字符，直到遍历完整个字符串。

时间复杂度 $O(n \times \Sigma)$ ，空间复杂度 $O(2^{\Sigma})$ ，其中 $\Sigma = 10$ ，而 $n$ 为字符串的长度。

相似题目：

1371. 每个元音包含偶数次的最长子字符串

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def wonderfulSubstrings(self, word: str) -> int:
        cnt = Counter({0: 1})
        ans = st = 0
        for c in word:
            st ^= 1 << (ord(c) - ord("a"))
            ans += cnt[st]
            for i in range(10):
                ans += cnt[st ^ (1 << i)]
            cnt[st] += 1
        return ans

speed

复杂度分析

指标	值
时间	O(NA)
空间	O(N)

psychology

面试官常问的追问

外企场景

question_mark
Candidate can apply bit manipulation to represent frequencies efficiently.
question_mark
Candidate identifies the need for a hash table to track frequency states over prefixes.
question_mark
Candidate recognizes the importance of reducing the problem complexity with prefix-based analysis.

warning

常见陷阱

外企场景

error
Failing to efficiently represent frequencies with a bitmask, leading to unnecessary complexity.
error
Not considering the need to track multiple occurrences of bitmask states using a hash table.
error
Overcomplicating the solution by checking all substrings individually instead of focusing on prefixes.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handling a larger set of characters beyond 'a' to 'j'.
arrow_right_alt
Optimizing the algorithm to handle even larger strings with stricter time limits.
arrow_right_alt
Exploring dynamic programming approaches to optimize the bitmask handling.

help

常见问题

外企场景

继续练习

#1930 长度为 3 的不同回文子序列 #1371 每个元音包含偶数次的最长子字符串 #1177 构建回文串检测