What is the primary pattern used in the 'Find the Longest Substring Containing Vowels in Even Counts' problem?

The primary pattern used in this problem is hash table plus bit manipulation. The problem is solved by tracking the parity of vowel counts using a bitmask, and hash tables are used to store the first occurrence of each bitmask.

How do you track vowel counts in the 'Find the Longest Substring Containing Vowels in Even Counts' problem?

Vowel counts are tracked using a bitmask, where each bit represents whether a specific vowel count is odd or even. By flipping the corresponding bit as you encounter each vowel, you can efficiently track the parity of the vowel counts.

Why is a hash table used in this problem?

The hash table stores the first occurrence of each bitmask, allowing us to calculate the length of the longest valid substring. By checking for repeated bitmasks, we can find substrings with even counts of vowels in linear time.

What is the time complexity of the 'Find the Longest Substring Containing Vowels in Even Counts' problem?

The time complexity is O(n), where n is the length of the string. This is because we iterate through the string once, performing constant-time operations for each character.

What are the key advantages of using bitmasking for this problem?

Bitmasking allows us to efficiently track the parity of each vowel count with constant space, and it avoids the need for nested loops or brute-force checks, ensuring the solution runs in linear time.

#1371

Medium

auto_awesome前缀和

LeetCode 题解工作台

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

给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 'a'，'e'，'i'，'o'，'u' ，在子字符串中都恰好出现了偶数次。示例 1：输入： s = "eleetminicoworoep" 输出： 13 解释：最长子字符串是 "leetminicowor" ，它…

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

题目描述

给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 'a'，'e'，'i'，'o'，'u' ，在子字符串中都恰好出现了偶数次。

示例 1：

输入：s = "eleetminicoworoep"
输出：13
解释：最长子字符串是 "leetminicowor" ，它包含 e，i，o 各 2 个，以及 0 个 a，u 。

示例 2：

输入：s = "leetcodeisgreat"
输出：5
解释：最长子字符串是 "leetc" ，其中包含 2 个 e 。

示例 3：

输入：s = "bcbcbc"
输出：6
解释：这个示例中，字符串 "bcbcbc" 本身就是最长的，因为所有的元音 a，e，i，o，u 都出现了 0 次。

提示：

1 <= s.length <= 5 x 10^5
s 只包含小写英文字母。

lightbulb

解题思路

方法一：前缀异或 + 数组或哈希表

根据题目描述，如果我们用一个数字表示字符串 $\textit{s}$ 的某个前缀中每个元音字母出现的次数的奇偶性，那么当两个前缀的这个数字相同时，这两个前缀的交集就是一个符合条件的子字符串。

我们可以用一个二进制数的低五位分别表示五个元音字母的奇偶性，其中第 $i$ 位为 $1$ 表示该元音字母在子字符串中出现了奇数次，为 $0$ 表示该元音字母在子字符串中出现了偶数次。

我们用 $\textit{mask}$ 表示这个二进制数，用一个数组或哈希表 $\textit{d}$ 记录每个 $\textit{mask}$ 第一次出现的位置。初始时，我们将 $\textit{d}[0] = -1$ ，表示空字符串的开始位置为 $-1$ 。

遍历字符串 $\textit{s}$ ，如果遇到元音字母，就将 $\textit{mask}$ 的对应位取反。接下来，我们判断 $\textit{mask}$ 是否在之前出现过，如果出现过，那么我们就找到了一个符合条件的子字符串，其长度为当前位置减去 $\textit{mask}$ 上一次出现的位置。否则，我们将 $\textit{mask}$ 的当前位置存入 $\textit{d}$ 。

遍历结束后，我们就找到了最长的符合条件的子字符串。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串 $\textit{s}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def findTheLongestSubstring(self, s: str) -> int:
        d = {0: -1}
        ans = mask = 0
        for i, c in enumerate(s):
            if c in "aeiou":
                mask ^= 1 << (ord(c) - ord("a"))
            if mask in d:
                j = d[mask]
                ans = max(ans, i - j)
            else:
                d[mask] = i
        return ans

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
The candidate uses bit manipulation effectively to represent the parity of vowel counts.
question_mark
The candidate applies hash tables to optimize the search for the longest valid substring.
question_mark
The candidate avoids using brute-force approaches that would lead to O(n^2) time complexity.

warning

常见陷阱

外企场景

error
Overcomplicating the problem by using nested loops instead of a linear pass with bit manipulation.
error
Failing to initialize the hash table properly and missing the base case where no vowels are encountered.
error
Not recognizing that the problem only involves vowel counts and misusing the bitmask for non-vowel characters.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to count vowels that appear an odd number of times instead of even.
arrow_right_alt
Extend the problem to include uppercase vowels and ensure case insensitivity.
arrow_right_alt
Allow other characters (e.g., punctuation) and ask for substrings with even vowel counts, ignoring non-alphabet characters.

help

常见问题

外企场景

继续练习

#1177 构建回文串检测 #1442 形成两个异或相等数组的三元组数目 #1525 字符串的好分割数目