题目描述

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

思路

①由于问题的规模在5×10⁵，因此需要使用O(n)的算法，否则在leetcode上会TLE。
②使用的算法是状态压缩，由于本题所判断的最长子列，需要五个元音字母出现偶数次，偶数次有以下性质：

• 0次也算偶数次，因此如果一个字符串从未出现过元音字母，那么它自身便是最长的子串。
• 当前状态下，如果某个元音字母再次出现偶数次，那么它的状态是不变的，因为偶数 + 偶数还是偶数。只有当遇到奇数次时，状态才会改变。
• 因此可以使用一个位图来记录某个状态上一次出现在哪个位置，一共有32个状态，即位图的00000~11111。
• 从头到尾线性遍历字符串，如果出现元音字母，寻找上一次（或者说，第一次出现的位置）它出现的位置。
• 直到下一次状态改变之前，前面的子串如果满足条件，那么就是最长的子串。出现偶数次不会改变状态，但是出现奇数次则会出现新的状态。出现新的状态时记录新的状态，否则更新原状态。

代码

class Solution {
public:
    int findTheLongestSubstring(string s) {
        vector<int> count(32,-2);
        count[0] = -1;  //第0个状态：所有元音字母均出现0次，此时i - count[0]即为字符串长度。
        int state = 0,res = 0;
        string cs = "aeiou";
        for(int i=0;i<s.size();i++){
            int k = cs.find(s[i]);
            if(k != -1){//找不到值，返回-1.
                state ^= 1 << k;
            }
            if(count[state] != -2)  res = max(res, i-count[state]);
            else                    count[state] = i;
        }
        return res;
    }
};