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

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

本题考查了前缀和的知识点。这个是我的盲区。一看到这道题字符串，又是统计最长子字符串，就想着滑动窗口，结果做了半天也没想到该怎么做，又想了想动态规划，好像也很复杂，无奈看了题解，居然还看了很久才明白题解的精简代码。。。

其实本题的思路是循序渐进的，一开始我们可以考虑用暴力枚举，那就是每个子字符串都进行统计，显然这个复杂度太高。
接着我们换一种思路，如何统计最长子字符串，假设该子字符串是以i为起点，j为终点，那其实就是0-j的长度减去0-i的长度，只要判断出每个前缀前中有多少元音，就可以解决本题了，知道每个前缀的原因其实就是通过前一个前缀加一个字母的判断即可，那请注意本题要判断每个元音包含偶数次，因此你需要一个二维数组去记录，那就是pre[i][k]代表的是前i个字母中，第k个原因出现的次数。

做到这里复杂度也优化了不少，但是没有充分利用条件中的偶数。
我们需要知道一件事，偶数减偶数是偶数，奇数减奇数也是偶数，因此我们只要知道每个前缀和的奇偶就可以了，我们不需要算出来前缀和里的元音个数，因此我们能进行状态压缩。
状态压缩成一个 0 - 32大小的数组， 00000代表每个数都是出现了偶数次，11111，代表每个数都出现了奇数次，那10000就代表其中一个数出现了奇数次，显然只有00000是满足条件的，但是也不尽然，因为我们说了奇数减奇数也是偶数。
我们假设一种情况是zzabbbb，只要我们排除了a出现的前缀和，那就是从b开始，每次都减去a出现的前缀和，那也是满足题目要求的。因此本题的难点就在于如何表示这种情况，其实当你想到了用状态压缩0，表示偶数，1表示奇数，你就能想到异或的运算，没遇见一个元音就对其代表的位数上进行异或运算。

口说无凭，我们来根据思路来跟踪算法。

• leetcodeisgreat
  初始化 status = 0, pre[0] = 0//因为前0个前缀和显然是0。ans = 0
  i = 0
  status = 0 , ans = 1
  i = 1
  status = 00010 pre[00010] = 2//就是这种情况下的前缀是2
  i = 2
  status = 00000 //遇见了第二个e，相互异或变为0 ans = max(max,i+1-pre[0])=3 //当status是0就代表每个数都是偶数，那显然从开头到结尾的子字符串满足答案的。
  i = 3
  status = 00000 ans = 4
  i = 4
  status = 00000 ans = 5
  i = 5
  status = 01000 pre[01000] = 6
  i = 6
  status = 01000 ans = (max,i + 1 - pre[01000]) //这一步就是减掉o的前缀和，那剩下的字符串就是满足答案了，如果大于ans，那就取这个值。
  .....
  我们可以发现这种状态压缩是非常巧妙的，pre数组把32种变化都保存了下来，还仅仅通过简单的异或就可以记录每次变化，然后还通过减法，当从开头到结尾出现了元音为1的子字符串，我们就去掉第一次出现元音为1的子字符串，就是满足答案的数了，真是巧妙。

代码如下:

class Solution {
    public int findTheLongestSubstring(String s) {

        int[] pre = new int[1<<5];
        Arrays.fill(pre,-1);
        pre[0] = 0;
        int n = s.length();
        int ans = 0,status = 0;
        for (int i = 0; i < n; i++){
            char c = s.charAt(i);
            if (c == 'a'){
                status ^= 1<<0;
            }
            else if (c == 'e'){
                status ^= 1<<1;
            }
            else if (c == 'i'){
                status ^= 1<<2;
            }
            else if (c == 'u'){
                status ^= 1<<3;
            }
            else if (c == 'o'){
                status ^= 1<<4;
            }
            //当访问过这个元音,或者是没有元音
            if (pre[status] >= 0){
                ans = Math.max(ans,i + 1 - pre[status]);
            }
            else{
                //记录该元音的前缀和
                pre[status] = i + 1;
            }

        }
        return ans;
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-longest-substring-containing-vowels-in-even-counts
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。