解法一

用前缀和的思想统计从第一位到其他当前位置的各个元音字母出现的次数。然后用5位二进制数对5个元音字母的奇偶状态进行编码，放进一个List，存储当前下标。最后针对各编码的下标数组（即不同的元音字母奇偶状态）计算其下标最大值和最小值之差，即可得到满足条件的子串的长度，再从中找出最大值即为答案。

  1. import java.util.List;
  2. import java.util.Map;
  3. import java.util.HashMap;
  4. import java.util.LinkedList;
  6. class Solution {
  7.     public int findTheLongestSubstring(String s) {
  8.         // 防止第一位影响计算
  9.         s = 'b' + s;
  11.         // 统计到当前位数各个元音字母的数量
  12.         int[][] count = new int[s.length()][5];
  14.         // 将有相同编码的下标放在同一数组中
  15.         Map<Integer, List<Integer>> indexMap = new HashMap<>();
  17.         // 用于计算编码
  18.         int key = 0;
  20.         for (int i = 0; i < s.length(); ++i) {
  21.             if (i > 0) {
  22.                 count[i] = count[i - 1].clone();
  23.             }
  24.             switch (s.charAt(i)) {
  25.                 case 'a':
  26.                     ++count[i][0];
  27.                     break;
  28.                 case 'e':
  29.                     ++count[i][1];
  30.                     break;
  31.                 case 'i':
  32.                     ++count[i][2];
  33.                     break;
  34.                 case 'o':
  35.                     ++count[i][3];
  36.                     break;
  37.                 case 'u':
  38.                     ++count[i][4];
  39.                     break;
  40.             }
  42.             // 根据各个元音字母个数奇偶情况编码
  43.             key = 0;
  44.             for (int j = 0; j < 5; ++j) {
  45.                 if (count[i][j] % 2 == 1) {
  46.                     key <<= 1;
  47.                     ++key;
  48.                 } else {
  49.                     key <<= 1;
  50.                 }
  51.             }
  53.             if (indexMap.containsKey(key)) {
  54.                 indexMap.get(key).add(i);
  55.             } else {
  56.                 LinkedList<Integer> list = new LinkedList<>();
  57.                 list.add(i);
  58.                 indexMap.put(key, list);
  59.             }
  60.         }
  62.         // 统计根据相同编码的对应下标计算满足条件的最大子串长度
  63.         int maxLength = 0;
  64.         for (List<Integer> list : indexMap.values()) {
  65.             maxLength = Math.max(
  66.                     maxLength,
  67.                     list.get(list.size() - 1) - list.get(0)
  68.             );
  69.         }
  71.         return maxLength;
  72.     }
  73. }

解法二

解法一是自己想完做出来的，但是一提交发现时间内存都比较糟糕，再去看官方题解：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/
其实前缀和和状态压缩的思想在解法一中都已经想到了，但是编码实现的方式上可以进一步提升。通过异或操作可以直接利用上一次奇偶状态，而不同编码对应的下标只需要存储最小值，也无需用复杂的Map。

  1. import java.util.Arrays;
  3. class Solution {
  4.     public int findTheLongestSubstring(String s) {
  5.         // 防止第一位影响计算
  6.         s = 'b' + s;
  8.         // 满足编码的最小下标
  9.         int[] keyArr = new int[1 << 5];
  10.         Arrays.fill(keyArr, -1);
  12.         // 当前奇偶状态
  13.         int key = 0;
  15.         // 最大长度
  16.         int maxLength = 0;
  18.         for (int i = 0; i < s.length(); ++i) {
  19.             switch (s.charAt(i)) {
  20.                 case 'a':
  21.                     key ^= 1 << 4;
  22.                     break;
  23.                 case 'e':
  24.                     key ^= 1 << 3;
  25.                     break;
  26.                 case 'i':
  27.                     key ^= 1 << 2;
  28.                     break;
  29.                 case 'o':
  30.                     key ^= 1 << 1;
  31.                     break;
  32.                 case 'u':
  33.                     key ^= 1 << 0;
  34.                     break;
  35.             }
  36.             if (keyArr[key] >= 0) {
  37.                 maxLength = Math.max(maxLength, i - keyArr[key]);
  38.             } else {
  39.                 keyArr[key] = i;
  40.             }
  41.         }
  43.         return maxLength;
  44.     }
  45. }

题外

在第一遍做的时候，我一开始想用泛型数组来做不同状态的下标数组，但是由于Java泛型的实现机制，泛型数组无法使用，所以用了Map。关于这个点可以参看以下知乎讨论。