1371.md

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 只包含小写英文字母。

---

解法一：
思路：

• 由题目中的全是偶数这个条件可以得知，我们可以通过验证奇偶性可以得知是否全是偶数了。
• 验证奇偶性我们可以通过 异或 运算，例如 aba：
  1. 初始时 status = 00000，然后到 a 的时候 00000 ^ 00001 = 00001，1 说明 a 出现 奇数 次
  2. 然后到 b 的时候 00001 ^ 00010 = 00011，两个 1 说明 a、b 都出现 奇数 次
  3. 最后到 a 的时候 00011 ^ 00001 = 00010，说明只有 b 出现 奇数 次了。
• 当求出一个坐标的状态码的时候，检测这个状态码值对应是否存有字符串索引值，如有，算出子串长度并与 max 值比较，取最大的值。
• 因为状态码的组合情况有 2^5 - 1 = 31 种，所以我们需要开辟一个 32 大小的数组对这些情况进行存储。
• dp[status] = i + 1 的意思是前 i + 1 个字符运算后的状态码为 status

class Solution {
    public int findTheLongestSubstring(String s) {
        int max = 0;
        int[] dp  = new int[1 << 5];
        int status = 0;
        Arrays.fill(dp, -1);
        dp[status] = 0;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == 'a') {
                status ^= (1 << 0);
            } else if (ch == 'e') {
                status ^= (1 << 1);
            } else if (ch == 'i') {
                status ^= (1 << 2);
            } else if (ch == 'o') {
                status ^= (1 << 3);
            } else if (ch == 'u') {
                status ^= (1 << 4);
            }
            if (dp[status] >= 0) {
                max = Math.max(max, i + 1 - dp[status]);
            } else {
                dp[status] = i + 1;
            }
        }
        return  max;
    }
}

复杂度分析：

• 时间复杂度：$O(n)$，其中 $n$ 为字符串 $s$ 的长度。我们只需要遍历一遍字符串即可求得答案，因此时间复杂度为 $O(n)$。
• 空间复杂度：$O(S)$，其中 $S$ 表示元音字母压缩成一个状态数的最大值，在本题中 $S = 32$。我们需要对应 $S$ 大小的空间来存放每个状态第一次出现的位置，因此需要 $O(S)$ 的空间复杂度。