1371、每个元音包含偶数次数的最长字符子串
给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 ‘a’，’e’，’i’，’o’，’u’ ，在子字符串中都恰好出现了偶数次。
示例 1：
输入：s = "eleetminicoworoep"
输出：13
解释：最长子字符串是 "leetminicowor" ，它包含 e，i，o 各 2 个，以及 0 个 a，u 。
示例 2：
输入：s = "leetcodeisgreat"
输出：5
解释：最长子字符串是 "leetc" ，其中包含 2 个 e 。
##示例 3：
输入：s = "bcbcbc"
输出：6
解释：这个示例中，字符串 "bcbcbc" 本身就是最长的，因为所有的元音 a，e，i，o，u 都出现了 0 次。
提示：
- $1 <= s.length <= 5 * 10^5$
- s 只包含小写英文字母。
链接：https://leetcode-cn.com/problems/find-the-longest-substring-containing-vowels-in-even-counts
题解
1、暴力枚举
遍历每一个子串，然后求出元音字母的个数，判断是否满足要求。
可惜超时了。
class Solution {
char[] vowels = {'a','e','i','o','u'};
public int findTheLongestSubstring(String s) {
char[] chs = s.toCharArray();
int res = 0;
for (int i = 0;i < chs.length;i++) {
for (int j = i;j < chs.length;j++) {
if (res > j-i+1) {
continue;
}
int[] chars = new int[26];
for (int k = i;k <= j;k++) {
chars[chs[k] - 'a']++;
}
boolean isVaild = true;
for (int k = 0;k < vowels.length && isVaild;k++) {
if (chars[vowels[k]-'a'] % 2 == 1) {
isVaild = false;
}
}
if (isVaild) {
res = Math.max(res,j-i+1);
}
}
}
return res;
}
}
前缀和 + 状态压缩
我们先来考虑暴力方法怎么做。最直观的方法无非就是枚举所有子串，遍历子串中的所有字符，统计元音字母出现的个数。如果符合条件，我们就更新答案，但这样肯定会因为超时而无法通过所有测试用例。
再回顾一下上面的操作，其实每个子串对应着一个区间，那么有什么方法可以在不重复遍历子串的前提下，快速求出这个区间里元音字母出现的次数呢？答案就是前缀和，对于一个区间，我们可以用两个前缀和的差值，得到其中某个字母的出现次数。
我们对每个元音字母维护一个前缀和，定义 $\textit{pre}[i][k]$] 表示在字符串前 i 个字符中，第 k 个元音字母一共出现的次数。假设我们需要求出 [l,r] 这个区间的子串是否满足条件，那么我们可以用 $pre[r][k]-pre[l-1][k]$，在 O(1) 的时间得到第 kk 个元音字母出现的次数。对于每一个元音字母，我们都判断一下其是否出现偶数次即可。
class Solution {
public int findTheLongestSubstring(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;
}
}
// 链接：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/
3、动态规划
dp[i]作为以字符串i位作为结尾的、满足要求的最长子串长度
- 如果i不是元音，那么
dp[i][j]=dp[i-1][j]+1 - 如果i是元音，那么找到它对应的位，假设是x，那么
dp[i][j] = dp[i-1][j xor x]
作者：he-yun-fei
链接：https://leetcode-cn.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/solution/javadong-tai-gui-hua-by-he-yun-fei/
class Solution {
public int findTheLongestSubstring(String s) {
char[] chars = new char[]{'a', 'e', 'i', 'o', 'u'};
int[] nums = new int[]{16, 8, 4, 2, 1};
int[][] dp = new int[s.length() + 1][32];
for (int i = 0; i <= s.length(); i++) for (int j = 0; j < 32; j++) dp[i][j] = -1;
dp[0][0] = 0;
int result = Integer.MIN_VALUE;
for (int i = 0; i < s.length(); i++) {
boolean found = false;
for (int j = 0; j < chars.length; j++)
if (chars[j] == s.charAt(i)) {
found = true;
for (int k = 0; k < 32; k++) if (dp[i][k] != -1) dp[i + 1][k ^ nums[j]] = dp[i][k] + 1;
dp[i + 1][0] = Math.max(0, dp[i + 1][0]);
}
if (!found) {
dp[i + 1][0] = dp[i][0] + 1;
for (int k = 1; k < 32; k++) if (dp[i][k] != -1) dp[i + 1][k] = dp[i][k] + 1;
}
result = Math.max(result, dp[i + 1][0]);
}
return result;
}
}
// 作者：he-yun-fei
// 链接：https://leetcode-cn.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/solution/javadong-tai-gui-hua-by-he-yun-fei/
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
