我对一类常考算法面试题的详细分析

给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 'a'，'e'，'i'，'o'，'u' ，在子字符串中都恰好出现了偶数次。

示例 1：

输入：s = "leetminicoworoep"
输出：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

2 分析过程

创建一个状态机：

• 对于非元音字符放置到位置0处，
• 元音字符'a'放置到位置1处，
• 元音字符'e'放置到位置2处，
• 元音字符'i'放置到位置4处，
• 元音字符'o'放置到位置8处，
• 元音字符'u'放置到位置16处

元音字符之所以放到1，2，4，8，16，是要为位运算创造条件，二进制表示中这些数字都只有1位为1，其他位置都为0. 很明显，为1的位置是标志位。

以处理leetcode字符串为例：

状态机有如下6个取值，非元音字符放置到0处：

处理第二个字符e时，放置到2处：

第三个字符又是e，再次放置到2处：

下面又是两个非元音字符，到字符c为止，字符串leetc就是满足题意(单个元音字符出现偶数次)的最大子字符串。

判断元音字符出现偶数次的方法：二进制表示下，且6个值(0,1,2,4,8,16)都只有一个位为1，所以使用异或运算，某个元音字符出现偶数次时，此位最终状态必然为0；奇数次时最终值必然为1.

接下来，处理下一个字符o，但是后面没有字符o，只出现1次，不满足题意：

接下来一样方法处理剩余字符，所以整个字符串满足题意的最长子串为：leetc

如果字符串修改为：leetcodoe，满足题意的最长子串：leetcodo.

3 代码

基于以上分析，再看下面代码就不难理解：

class Solution(object):
    def findTheLongestSubstring(self,s):
        state, statedict =  0, {0:-1} #设置此初始值决定下面的代码 i-statedict[state] 这样写
        maxlen = 0
        codedict = {'a':1,'e':2,'i':4,'o':8,'u':16}
        for i,c in enumerate(s):
            if c in codedict:
                state ^= codedict[c]
            if state in statedict:
                maxlen = max(maxlen,i-statedict[state])
            else:
                statedict[state] = i # 记忆新的状态值，二进制位下，可能会出现类似"第1位或第3位为1"的32种组合
        return maxlen

statedict 设置{0:-1}初始值，也是很有讲究、很巧妙的，决定了下面的代码 i-statedict[state] 这样写

statedict[state] = i 记忆新的状态值，二进制位下，可能会出现类似第1位或第3位为1的32种组合。

4 扩展

今天题目与Day50的思路极为类似，Day50: 连续数组，可以归纳为前缀和问题。

此类问题关键是想办法巧妙的处理各种状态，区分各种状态。记忆某种状态，中间经历某种变换或抵消操作后，出现了状态字典里的某个状态，表明找到满足题意的前缀。

比如，字符串lee，第一个状态是l，第二个是le，第三个状态又是l，因为2个e能抵消。因此，满足题意的最长子串长度为3.

字符串oeo，第一个状态是o，第二个状态oe，第三个状态是e，两个o抵消，因此没有重复状态。因此，满足题意的最长子串长度为0.