题目链接:https://leetcode-cn.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/
题目描述
分析
1. 数组记录元音下标
时间负责度:O(n) a. 获取元音下标，存储到数组中 b. 数组长度0:没有元音，返回字符串长度;1:只有一个元音，去元音两侧最长的;偶数:最大下标-最小下标;奇数:去掉一侧后，取最长的
代码实现
public enum Q1371 {
instance;
//eleetminicoworoep :原字符
//0 2 3 6 8 10 12 14 15 :下标
// 1. 获取元音下标
// 2. 最大最小偶数差
public int findTheLongestSubstring(String s) {
List<Integer> vowels = new ArrayList<>();
for(int i=0;i<s.length();i++){
if(isVowel(s.charAt(i))){
vowels.add(i);
}
}
int size=vowels.size();
if(size==0){
return s.length();
}else if(size==1){
int a=vowels.get(0);
int b=s.length()-1-a;
return a>b?a:b;
}
// 偶数
else if(size%2==0){
return vowels.get(size-1)-vowels.get(0);
// 奇数
}else {
int a = vowels.get(size-1)-vowels.get(1);
int b = vowels.get(size-2)-vowels.get(0);
return a>b?a:b;
}
}
private boolean isVowel(char c){
return c=='a'||c=='e'||c=='i'||c=='o'||c=='u';
}
public int findTheLongestSubstring2(String s){
int n = s.length();
int[] pos = new int[1 << 5];
Arrays.fill(pos, -1);
int ans = 0, status = 0;
pos[0] = 0;
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (ch == 'a') {
status ^= (1 << 0);
} else if (ch == 'e') {
status ^= (1 << 1);
} else if (ch == 'i') {
status ^= (1 << 2);
} else if (ch == 'o') {
status ^= (1 << 3);
} else if (ch == 'u') {
status ^= (1 << 4);
}
if (pos[status] >= 0) {
ans = Math.max(ans, i + 1 - pos[status]);
} else {
pos[status] = i + 1;
}
}
return ans;
}
public static void main(String[] args) {
// assert 13
System.out.println(Q1371.instance.findTheLongestSubstring2("eleetminicoworoep"));
}
}
