本文共 1337 字，大约阅读时间需要 4 分钟。

给你一个字符串 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 只包含小写英文字母。

解题思路

这个问题和类似，由于只需要记录元音字符出现次数是不是偶数次，那么我们可以通过0表示偶数，而1表示奇数，只需要通过5bit个数字即可表示到当前位置的所以元音字符奇偶状态。如果前后两个状态相同，那么说明这两个状态之间的元音字符个数满足条件，例如：

e l e e t m i n i c o w o r o e p↑         ↑  l         r-----------------------------------l: 01000r: 01000

为了记录最长字符串，那么我们只需记录元音字符奇偶状态出现的第一个位置，例如上面这个例子，我们最后只记录l的位置，因为l将距离更远。

class Solution:    def findTheLongestSubstring(self, s: str) -> int:        vis = {
   0: -1}        vowels = collections.defaultdict(int)        for i, c in enumerate("aeiou"): vowels[c] = 1 << (i + 1) >> 1                    res = cur = 0        for i, c in enumerate(s):            cur ^= vowels[c]            vis.setdefault(cur, i)            res = max(res, i - vis[cur])        return res

说明一下：上面写法中(1 << vis[c]) >> 1比较奇特，原因在于a,e,i,o,u可以通过1,2,4,8,16表示，而其他字符就通过0表示。（>>1的目的就是不希望其他字符参与状态表示）

reference:

https://leetcode.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/discuss/531840/JavaC%2B%2BPython-One-Pass

我将该问题的其他语言版本添加到了我的

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/104757225 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！