这一题我们只需要关心子字符串中的元音字母个数是奇数还是偶数,并不关心到底每一个字符有多少个。所以一个子字符串 s[0,i] 可以用一个 5 位的 2进制数来表示。
那么总共的状态一共就有 32种
再看, 我们假设现在 s[0,i] 的状态为 01001,并且对于以 i 结尾的子字符串,其中 s[j+1,i]是满足题意的最长子字符串,那么可以推出 s[0,j]的状态与 s[0,i]相同。因为奇数-奇数=偶数,偶数-偶数=偶数。
这样才可以使得是 s[j+1,i] 满足,每个元音字母,即 ‘a’,’e’,’i’,’o’,’u’在子字符串中都恰好出现了偶数
那么对于每一个子字符串,都有一个状态 state, 我们需要记录下这个状态上一次出现的位置。
然后相减得到结果的长度,取最大值就可以得到答案。
时间复杂度为 $O(n)$
至于为啥cnt[0]要初始化为 -1 ,参考题解
Java 代码
class Solution {
public int findTheLongestSubstring(String s) {
int []cnt=new int[32];
Arrays.fill(cnt,-2);
cnt[0]=-1;
String ys="aeiou";
int state=0;
char [] str= s.toCharArray();
int res=0;
for(int i=0;i<str.length;i++){
int k=ys.indexOf(str[i]);
if(k!=-1){
state^=1<<k;
}
if(cnt[state]!=-2){
res=Math.max(res,i-cnt[state]);
}else{
cnt[state]=i;
}
}
return res;
}
}