原文链接: https://leetcode-cn.com/problems/find-the-longest-substring-containing-vowels-in-even-counts

英文原文

Given the string s, return the size of the longest substring containing each vowel an even number of times. That is, 'a', 'e', 'i', 'o', and 'u' must appear an even number of times.

 

Example 1:

Input: s = "eleetminicoworoep"
Output: 13
Explanation: The longest substring is "leetminicowor" which contains two each of the vowels: e, i and o and zero of the vowels: a and u.

Example 2:

Input: s = "leetcodeisgreat"
Output: 5
Explanation: The longest substring is "leetc" which contains two e's.

Example 3:

Input: s = "bcbcbc"
Output: 6
Explanation: In this case, the given string "bcbcbc" is the longest because all vowels: a, e, i, o and u appear zero times.

 

Constraints:

• 1 <= s.length <= 5 x 10^5
• s contains only lowercase English letters.

中文题目

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

通过代码

高赞题解

解题思路：

将 $5$ 个元音字母出现次数的奇偶视为一种状态，一共有 $32$ 种状态，不妨使用一个整数代表状态，第 $0$ 位为 $1$ 表示 a 出现奇数次，第一位为 $1$ 表示 e 出现奇数次……以此类推。仅有状态 $0$ 符合题意。

而如果子串 [0，i] 与字串 [0,j] 状态相同，那么字串 [i+1,j] 的状态一定是 $0$，因此可以记录每个状态第一次出现的位置，此后再出现该状态时相减即可。
需要注意状态 $0$ 首次出现的位置应该设定为 -1。

在计算状态的时候可以利用异或运算。

[]
class Solution {
public:
    int findTheLongestSubstring(string s) {
        vector<int> pre(32,INT_MAX);
        pre[0]=-1;
        const int N=s.size();
        int cur=0;
        int ans=0;
        for(int i=0;i<N;++i){
            switch(s[i]){
                case 'a':cur^=1;break;
                case 'e':cur^=2;break;
                case 'i':cur^=4;break;
                case 'o':cur^=8;break;
                case 'u':cur^=16;break;
                default:break;
            }
            if(pre[cur]==INT_MAX) pre[cur]=i;
            else ans=max(ans,i-pre[cur]);
        }
        return ans;
    }
};

统计信息

通过次数	提交次数	AC比率
21579	37164	58.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言