每个元音包含偶数次的最长子字符串 图解题解

这道题到底在问什么

输入

s = "leetcode"

输出

5(子串 "leetc",e 出现 2 次,其余元音 0 次)

输入

s = "bcbcbc"

输出

6(整串没有元音,全部元音都是 0 次)

最优解：一步一步想明白

1. 3记牢一句话:用 5 位掩码记五个元音的奇偶,扫到当前掩码和之前某下标的掩码相等,中间这段就全偶。下面每一帧都在套这个思路。
2. 4开扫之前先看舞台。上面这排是字符串 "leetcode" 的每个字符。右边面板是状态首现表 d,现在只有一行:状态 00000 配下标 -1。00000 表示五个元音此刻都出现偶数次(都是 0 次),这就是空前缀的状态。把它的首现下标定成 -1,代表它出现在整个字符串开头之前,这个哨兵待会儿处理从头就全偶的子串时非常关键。
3. 5说清楚掩码怎么读。它是五位,从左到右依次对应 a、e、i、o、u。某一位是 0 表示那个元音到目前为止出现了偶数次,是 1 表示奇数次。比如 01000 就表示只有 e 出现了奇数次,其余四个都是偶数次。扫描过程中,每遇到一个元音,就把它对应的那一位由 0 翻成 1 或者由 1 翻回 0,这正好对应「次数加一,奇偶反转」。
4. 6扫到下标 0 的字符 "l",它不是元音,对五个元音的奇偶毫无影响,所以掩码原封不动,还是 00000。非元音字符可以自由地待在子串里,从不破坏全偶这个条件。
5. 7查表发现状态 00000 不是第一次见,它最早出现在下标 -1。这说明从下标 0 到 0 这一段里,每个元音都被翻了偶数次,正好全偶,长度是 0 减 -1 等于 1。比之前记的最长还大,所以把答案刷新成 1,这段就是目前最优的子串。
6. 8扫到下标 1 的字符 "e",它是元音,所以把掩码里 e 那一位翻一下。翻之前是 00000,翻之后变成 01000,意思是 e 的出现次数奇偶性反过来了。其余四位保持不动。
7. 9查表发现状态 01000 还没出现过,这是第一次见。那就把它记进表里,首现下标设为 1。为什么只在第一次见时记、而且永远不覆盖?因为我们要的是最长子串,同一个状态留着它最早的下标,将来再遇到同状态时,当前下标减这个最早下标才会最大。
8. 10扫到下标 2 的字符 "e",它是元音,所以把掩码里 e 那一位翻一下。翻之前是 01000,翻之后变成 00000,意思是 e 的出现次数奇偶性反过来了。其余四位保持不动。
9. 11查表发现状态 00000 不是第一次见,它最早出现在下标 -1。这说明从下标 0 到 2 这一段里,每个元音都被翻了偶数次,正好全偶,长度是 2 减 -1 等于 3。比之前记的最长还大,所以把答案刷新成 3,这段就是目前最优的子串。
10. 12在这里停一下,体会为什么掩码相等就等于全偶。下标 1、2 两个 "e" 让 e 这一位先翻成奇、又翻回偶,掩码从 00000 走了一圈又回到 00000。现在它和哨兵下标 -1 那个 00000 相等。两个相等的状态之间,每个元音的奇偶都没变,等价于每个元音都被翻了偶数次,所以中间这段 "lee" 里 e 出现 2 次、其余元音 0 次,确实全偶。这就是整道题的根。
11. 13扫到下标 3 的字符 "t",它不是元音,对五个元音的奇偶毫无影响,所以掩码原封不动,还是 00000。非元音字符可以自由地待在子串里,从不破坏全偶这个条件。
12. 14查表发现状态 00000 不是第一次见,它最早出现在下标 -1。这说明从下标 0 到 3 这一段里,每个元音都被翻了偶数次,正好全偶,长度是 3 减 -1 等于 4。比之前记的最长还大,所以把答案刷新成 4,这段就是目前最优的子串。
13. 15扫到下标 4 的字符 "c",它不是元音,对五个元音的奇偶毫无影响,所以掩码原封不动,还是 00000。非元音字符可以自由地待在子串里,从不破坏全偶这个条件。
14. 16查表发现状态 00000 不是第一次见,它最早出现在下标 -1。这说明从下标 0 到 4 这一段里,每个元音都被翻了偶数次,正好全偶,长度是 4 减 -1 等于 5。比之前记的最长还大,所以把答案刷新成 5,这段就是目前最优的子串。
15. 17扫到下标 5 的字符 "o",它是元音,所以把掩码里 o 那一位翻一下。翻之前是 00000,翻之后变成 00010,意思是 o 的出现次数奇偶性反过来了。其余四位保持不动。
16. 18查表发现状态 00010 还没出现过,这是第一次见。那就把它记进表里,首现下标设为 5。为什么只在第一次见时记、而且永远不覆盖?因为我们要的是最长子串,同一个状态留着它最早的下标,将来再遇到同状态时,当前下标减这个最早下标才会最大。
17. 19扫到下标 6 的字符 "d",它不是元音,对五个元音的奇偶毫无影响,所以掩码原封不动,还是 00010。非元音字符可以自由地待在子串里,从不破坏全偶这个条件。
18. 20查表发现状态 00010 不是第一次见,它最早出现在下标 5。这说明从下标 6 到 6 这一段里,每个元音都被翻了偶数次,正好全偶,长度是 6 减 5 等于 1。不过它没有超过当前已经记下的最长 5,所以答案保持不变。注意这里不更新表里的下标,因为要的是最早出现的位置,留着它才能在以后配出更长的段。
19. 21扫到下标 7 的字符 "e",它是元音,所以把掩码里 e 那一位翻一下。翻之前是 00010,翻之后变成 01010,意思是 e 的出现次数奇偶性反过来了。其余四位保持不动。
20. 22查表发现状态 01010 还没出现过,这是第一次见。那就把它记进表里,首现下标设为 7。为什么只在第一次见时记、而且永远不覆盖?因为我们要的是最长子串,同一个状态留着它最早的下标,将来再遇到同状态时,当前下标减这个最早下标才会最大。
21. 23扫描结束前看一眼这张表,它一共记下了 4 种不同的奇偶状态,每种都只存了第一次出现的下标。哪怕字符串再长,这张表也最多 32 行,因为五个元音的奇偶组合总共就 32 种。整个算法的省力之处,就是把数元音这件累活,换成了在这张小表里查状态有没有见过。
22. 24整个字符串扫完了。绿色高亮的就是最长的全偶子串 "leetc",下标 0 到 4,长度 5。回放一下关键点:当 i 走到 4 时掩码是 00000,和哨兵下标 -1 相等,于是子串 [0 到 4] 全偶,长度 5,这就是答案。后面下标 5 的 "o" 让 o 变成奇数,状态变了,再也凑不出更长的全偶段。全程只扫一遍,每一步查表都是常数时间。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def findTheLongestSubstring(self, s: str) -> int:
        d = {0: -1}
        ans = mask = 0
        for i, c in enumerate(s):
            if c in "aeiou":
                mask ^= 1 << (ord(c) - ord("a"))
            if mask in d:
                j = d[mask]
                ans = max(ans, i - j)
            else:
                d[mask] = i
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int findTheLongestSubstring(string s) {
        string vowels = "aeiou";
        vector<int> d(32, INT_MAX);
        d[0] = 0;
        int ans = 0, mask = 0;
        for (int i = 1; i <= s.length(); ++i) {
            char c = s[i - 1];
            for (int j = 0; j < 5; ++j) {
                if (c == vowels[j]) {
                    mask ^= 1 << j;
                    break;
                }
            }
            ans = max(ans, i - d[mask]);
            d[mask] = min(d[mask], i);
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int findTheLongestSubstring(String s) {
        String vowels = "aeiou";
        int[] d = new int[32];
        Arrays.fill(d, 1 << 29);
        d[0] = 0;
        int ans = 0, mask = 0;
        for (int i = 1; i <= s.length(); ++i) {
            char c = s.charAt(i - 1);
            for (int j = 0; j < 5; ++j) {
                if (c == vowels.charAt(j)) {
                    mask ^= 1 << j;
                    break;
                }
            }
            ans = Math.max(ans, i - d[mask]);
            d[mask] = Math.min(d[mask], i);
        }
        return ans;
    }
}

复杂度

面试官可能追问