题目描述

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

样例

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

算法1

状态压缩 $O(n)$

根据题目意思，我们只需要知道a,e,i,o,u这几个元音字母出现了奇数次还是偶数次，而不需要知道具体出现了多少次。所以我们可以用1表示每个字母出现了奇数次，0表示每个字母出现了偶数次。如果用二进制编码来表示对应的状态就是00000-11111(uoiea)，例如10010表示u出现了奇数次，o出现了偶数次，i出现了偶数次..。总共就有32种状态。我们根据异或运算的特点——不带进位的加法，来更新状态。通过维护一个数组，来存储第一次出现某个状态的位置。线性扫描时，对于当前的这个状态，用 i 减去第一次出现这个状态的位置，就能得到一个以 i 结尾的极大子区间。

时间复杂度 $O(n)$

参考文献

java 代码

 public int findTheLongestSubstring(String s) {
        //u o i e a
        //0 0 0 0 0 - 1 1 1 1 1表示每个字符出现了奇数次还是偶数次;
        int status = 0;
        int[] pos = new int[32];
        Arrays.fill(pos,-2);
        pos[0] = -1;
        int res = 0;
        for(int i = 0;i < s.length();i++){
            char c = s.charAt(i);
            switch(c){
                case 'a':
                    status ^= 1;
                    break;
                case 'e':
                    status ^= (1 << 1);
                    break;
                case 'i':
                    status ^= (1 << 2);
                    break;
                case 'o':
                    status ^= (1 << 3);
                    break;
                case 'u':
                    status ^= (1 << 4);
                    break;
                default:
                    break;
            }
            if(pos[status] < -1){
                pos[status] = i;
            }else{
                res = Math.max(res,i - pos[status]);
            }
        }
        return res;
    }