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

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

题目描述：

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

数据范围：
$ 1\le s.length \le 5 \times 10^5 $

s 只包含小写英文字母。

题解：

首先可以想到使用前缀和的方法，把每个元音字母出现的次数都记录下来，然后作差得到结果。

但是需要枚举起点和终点，时间复杂度会爆炸。然后可以想到使用unordered_map 哈希一下，只需要查找当前状态是否存在就行。这样的话就需要使用状态压缩，使用二进制，将元音字母出现的奇偶性转化为单个数字。

使用二进制位，1表示出现次数为奇数，0表示出现次数为偶数。从前往后每次进行异或操作（异或也是一种加法），如果mp中未出现过该状态，那么 mp[status] = i + 1 （注意是 i+1 因为是需要从下个位置开始计；出现过该状态，那么长度为 i-mp[status]+1 更新答案就好。

代码：

class Solution
{
public:
    int findTheLongestSubstring(string s)
    {
        unordered_map<int, int> mp;
        char aa[10] = "aeiou";
        int tmp = 0;
        int ans = 0;
        mp[0] = 0;
        for (int i = 0; i < s.length(); i++)
        {
            for (int j = 0; j < 5; j++)
            {
                if (s[i] == aa[j])
                {
                    tmp ^= (1 << (s[i] - 'a'));
                    break;
                }
            }
            if (mp.count(tmp))
            {
                ans = max(ans, i - mp[tmp] + 1);
            }
            else
            {
                mp[tmp] = i + 1;
            }
        }
        return ans;
    }
};