题目描述

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

样例

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

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

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

限制

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

算法

(状压，哈希表) $O(n)$

1. 我们只需要关注 5 个字母的奇偶性，所以可以用一个长度为 2^5 的掩码表示闭区间 [0, i] 的状态。
2. 维护一个哈希表，存储第一次出现这个掩码的位置。
3. 线性扫描时，对于当前的一个掩码，用 i 减去第一次出现这个掩码的位置，就能得到一个以 i 结尾的极大子区间。

时间复杂度

• 每个位置仅遍历一次，掩码和哈希表更新查询的时间都是常数，故总时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int findTheLongestSubstring(string s) {
        int n = s.length();
        const char c[5] = {'a', 'e', 'i', 'o', 'u'};

        vector<int> h(32, n + 1);
        h[0] = -1;

        int ans = 0;
        int mask = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 5; ++j)
                if (s[i] == c[j])
                    mask ^= 1 << j;

            ans = max(ans, i - h[mask]);
            h[mask] = min(h[mask], i);
        }

        return ans;
    }
};