1371.每个元音包含偶数次的最长子字符串

https://leetcode-cn.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/

• 1371.每个元音包含偶数次的最长子字符串

  • 题目描述

    • 方法 1：暴力+剪枝

  • 思路

  • 复杂度分析

  • 代码

    • 方法 2：前缀和

  • 思路

  • 复杂度分析

  • 代码

    • 方法 3：前缀和+状态压缩

  • 思路

  • 代码

题目描述

给你一个字符串 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法 1：暴力+剪枝

思路

• 先假设子串长度是 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,
        );
    }
};

方法 2：前缀和

思路

• 比较直白的思路是，构建前缀和数组 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;
    }
};

方法 3：前缀和+状态压缩

思路

这题跟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