https://leetcode-cn.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/
给你一个字符串 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 x 10^5
s 只包含小写英文字母。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-longest-substring-containing-vowels-in-even-counts
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
- 先假设子串长度是
s.length，检查这个子串是否满足条件。 - 然后将子串长度减一，枚举这个长度的所有子串，分别检查它们是否包含偶数次数的元音字母。
- 然后将子串长度减一，不断重复上一个步骤，直到找到满足条件的子串。
- 这里的剪枝思想是，我们先从最长的子串 (
s.length) 开始枚举，这样找到一个符合条件的子串就可以直接返回了。
- 时间复杂度：$O(N^3)$, N 为数组长度。枚举所有子串的复杂度是
$O(N^2)$ ，计算元音字母个数的复杂度是$O(N)$ 。 - 空间复杂度：$O(1)$。
JavaScript Code
/**
* @param {string} s
* @return {number}
*/
var findTheLongestSubstring = function (s) {
for (let subStrLen = s.length; subStrLen >= 0; subStrLen--) {
let remove = s.length - subStrLen + 1;
for (let start = 0; start < remove; start++) {
let subStr = s.slice(start, start + subStrLen);
if (hasEvenVowels(subStr)) return subStrLen;
}
}
// *********************************
function hasEvenVowels(s) {
const vowels = ['a', 'e', 'i', 'o', 'u'];
return !vowels.some(
v => (s.match(new RegExp(v, 'g')) || []).length % 2 !== 0,
);
}
};- 比较直白的思路是，构建前缀和数组
prefix，计算以 i 结束的子串中每个元音出现的次数。 - 然后遍历前缀和数组，找到所有满足条件的
[i, j]区间， - 满足条件即
prefix[j]中每个元音出现次数减去prefix[i]中每个元音出现次数刚好都是偶数。
- 时间复杂度：$O(N^2)$, N 为数组长度，枚举所有子串的复杂度是
$O(N^2)$ 。 - 空间复杂度：$O(N)$。
JavaScript Code
/**
* @param {string} s
* @return {number}
*/
var findTheLongestSubstring = function (s) {
const vowels = {
a: 0,
e: 1,
i: 2,
o: 3,
u: 4,
};
// 前缀和数组
const prefix = Array(s.length)
.fill(0)
.map(() => Array(5).fill(0));
for (let i = 0; i < s.length; i++) {
const c = s[i];
// 计算 [0, i] 区间每个元音出现的次数
// 我就直接调 API 复制上一个数组了 ╮(╯▽╰)╭
if (prefix[i - 1]) prefix[i] = prefix[i - 1].slice(0);
if (c in vowels) prefix[i][vowels[c]]++;
}
// 枚举子串，i 是子串长度
// 先从最长的子串开始枚举，是一个剪枝小技巧
for (let i = s.length - 1; i >= 0; i--) {
// j 是子串开头，i+j 是子串结束
for (let j = 0; j < s.length - i; j++) {
// 检查子串中元音出现次数，如果有满足条件的，直接返回
if (check(s, prefix, j, i + j)) return i + 1;
}
}
return 0;
// ********************************
function check(s, prefix, l, r) {
for (let i = 0; i < 5; i++) {
// 左边界 - 右边界
let cnt = prefix[r][i] - prefix[l][i];
// 把减掉的左边界再加上
cnt += vowels[s[l]] === i ? 1 : 0;
if (cnt % 2 !== 0) return false;
}
return true;
}
};这题跟560.和为 K 的子数组有一点点像，不过 560 只需要记录元素和就好了，本题有 5 个元音，状态要稍复杂一点。
- 其实我们不关心每个元音字母具体出现多少次，只要出现次数是偶数就可以了，所以我们可以只记录每个元音字母出现次数的奇偶性
- 如果两个数奇偶性相同，那他们的差肯定是偶数，也就是说，如果有一个区间
[i, j]满足prefix[i]和prefix[j]相同 (prefix 数组记录的是每个元音字母出现次数的奇偶性)，那这个区间就是符合题目条件的。
TODO
算了，不想写了
JavaScript Code
/**
* @param {string} s
* @return {number}
*/
var findTheLongestSubstring = function (s) {
const vowels = {
a: 0,
e: 1,
i: 2,
o: 3,
u: 4,
};
const seen = {
0: -1,
};
let status = 0,
ans = 0;
for (let i = 0; i < s.length; i++) {
if (s[i] in vowels) status ^= 1 << vowels[s[i]];
// 如果相同的奇偶性出现过，更新 ans
if (status in seen) {
ans = Math.max(ans, i - seen[status]);
}
// 否则记录当前下标
else {
seen[status] = i;
}
}
return ans;
};更多题解可以访问：https://github.com/suukii/91-days-algorithm