给定一个字符串，寻找一个最长子字符串，使得包含的原因字母都是偶数个。
我们很容易想到，暴力枚举。然后通过一点点巧妙的减支，可以通过。
首先扫一遍字符串，统计每个字符出现的次数。实际上我们只关注元音字母，不过直接全部统计比较方便（我估计时间上也会快一点）
然后我们枚举 i ~ j ,i 从0 到 len ， j 从 len到 i。然后判断 i j组成的子字符串是否符合要求。
注意两个剪枝条件： 如果 i - len 的长度小于已知的最大值，则 结束。
如果 i - j 的距离小于已知的最大值，则结束。
public static int findTheLongestSubstring(String s) { int maxLength = -1; int[] count = new int[26]; int len = s.length(); for(int i=0;i<len;i++){ count[s.charAt(i)-'a']++; } char[] Vowels = new char[]{'a','e','i','o','u'}; int vowelsEvenNum = 0; for(int i=0;i<5;i++){ if(count[Vowels[i]-'a']%2==0) vowelsEvenNum++; } if(vowelsEvenNum==5) return len; for(int i=0;i<len;i++){ if(len-i<maxLength) break; if(i>0) count[s.charAt(i-1)-'a']--; int[] tmp = count.clone(); for(int j=len-1;j>=i;j--){ if(maxLength>j-i+1) break; if(j<len-1) tmp[s.charAt(j+1)-'a']--; vowelsEvenNum=0; for(int k=0;k<5;k++){ if(tmp[Vowels[k]-'a']%2==0) vowelsEvenNum++; } if(vowelsEvenNum==5){ maxLength=Math.max(maxLength,j-i+1); } } } return maxLength;
我们优化一下。首先想到前缀和。 我们用 pre[i][k]表示第i个字符前，字符k有多少个。
则我们的子字符串满足：对于任意的k pre[i][k] - pre[j][k] 是偶数。同样的枚举 i , j 。 我估计上面的剪枝同样有效。
但是有新的优化，我们小学数学学过：
奇数-奇数=偶数
偶数-偶数=偶数
所以我们其实不用记录每个字符出现的个数，只需记录每个字符的奇偶性就可以了。这样的话，我们设计一个特殊的key：
{ a:，e: ,i: ,o:, u:} *:表示*字符的奇偶性。我们利用这样的特殊结构当做key，存储它第一次出现的位置。我们就可以利用哈希表通过一次遍历解决。
大概代码是这样的：
Map<STA, Integer> poss = new HashMap<>(); for (int i = 0; i < s.length(); i++) { STA sta = new STA(); if (s.charAt(i) == 'a') sta.a ^= 1; if (s.charAt(i) == 'e') sta.e ^= 1; if (s.charAt(i) == 'i') sta.i ^= 1; if (s.charAt(i) == 'o') sta.o ^= 1; if (s.charAt(i) == 'u') sta.u ^= 1; if (poss.containsKey(sta)) { ans = Math.max(ans, i - poss.get(sta) + 1); } else { poss.put(sta, i); }
这里我们要新加一个STA的类，而且要重写equal和hashCode方法。不太友好。其实我们只是用到了5个字母。我们用二进制来表示这个5个字母的奇偶性。1表示奇数个，0表示偶数个。我们只需要一个1<<5长度的数组就可以罗列所有状态（出现了出现了，有一个装逼利器：状态压缩）
这里有个编程的技巧。我们把00000，即所有字母都是偶数个的状态的位置设为0. 其他状态的位置设置为 i+1 .。这是符合逻辑的，因为一个都不选，长度为0，所有的元音字母的个数都为偶数。
然后这样的话，当一个状态出现两次的时候，它的长度就是 i+1 - pos[status]，这样就不用考虑边界值的问题了。
public static int findTheLongestSubstring2(String s) { int ans = 0; int[] pos = new int[1 << 5]; int status = 0; Arrays.fill(pos, -1); char[] sChar = s.toCharArray(); int len = s.length(); pos[0] = 0; for (int i = 0; i < len; i++) { char c = s.charAt(i); if (c == 'a') status ^= 1 << 0; if (c == 'e') status ^= 1 << 1; if (c == 'i') status ^= 1 << 2; if (c == 'o') status ^= 1 << 3; if (c == 'u') status ^= 1 << 4; if (pos[status] >= 0) ans = Math.max(ans, i + 1 - pos[status]); else pos[status] = i + 1; } return ans; }