题目描述

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

样例

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

算法1

(状态压缩) $O(n)$

这题甚为巧妙，pos数组存储特定元音奇偶性第一次出现的位置，再次出现相同状态时，说明这两个位置间的元音都是偶数个，更新答案即可。

时间复杂度

遍历字符串一次，所以时间复杂度O(n);
一共有$2^s$个状态，s为元音个数，所以空间复杂度时O(1 << s);

参考文献

https://leetcode-cn.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/solution/mei-ge-yuan-yin-bao-han-ou-shu-ci-de-zui-chang-z-2/

C++ 代码

class Solution {
public:
    int findTheLongestSubstring(string s) {
        vector<int> pos(1 << 5, -1);
        const char vowels[] = {'a', 'e', 'i', 'o', 'u'};
        int n = s.size(), status = 0, res = 0;
        pos[0] = 0;

        for (int i = 0; i < n; ++i){
            char c = s[i];
            for (int j = 0; j < 5; ++j){
                if (c == vowels[j]) status ^= 1 << j;
            }

            if (~pos[status]){
                res = max(res, i - pos[status] + 1);
            }
            else pos[status] = i + 1;
        }
        return res;
    }
};