算法：每个元音包含偶数次的最长字符串

发布日期: 2020-05-20

题目

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

示例 1：

1
2
3

输入：s = "eleetminicoworoep"
输出：13
解释：最长子字符串是 "leetminicowor" ，它包含 e，i，o 各 2 个，以及 0 个 a，u 。

示例 2：

1 2	输出：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

分析

这道题目我拿到手上第一个想法就是动态规划。如果你也跟我一样的想法，那就说明你的思路到目前是对的。来，让我们重温一下动态规划的做题思路：

建立数组
创建状态转化方程
遍历得出最终答案

第一步很容易想到，因为是一个字符串，所以我们可以建立一个一维数组来记录字符串的长度。然后接下来是最难的地方：如何记录最长的字符串？如何进行状态转换？哪一个是最终答案？这几个问题解决了，也就解决这道题了。接下来我一步步说。

首先我们的重点放在，如何进行动态转换。这就涉及两个问题：记录已遍历的字符串的信息；增加一个字符后转换的信息。这是动态规划题目的重点，我们要从题目的特殊性入手。
从这道题我们可以看到是求元音是偶数，每个元音都必须是偶数。我们假设字符串从 i 到 j 位之间是偶数，那么 0 到 i-1 ，和 0 到 j 的各个元音的奇偶性是一样的。为什么？偶数+偶数=偶数，奇数+偶数=奇数，而 i 到 j 是偶数，那么0到i-1和0到j奇偶性肯定一致。能够想到这个点后面就比较顺畅了。
现在我们知道最长字符串的特征了，那我们要做的就是，当遍历到第i位时，如何找到奇偶性和他相同且最靠前的字符串？假如元音只有a，那我们只需要记录两个位置：a是偶数的位置最小值和a是奇数的位置最小值。当我们不断遍历字符串时，根据遍历的字符得到已经遍历的字符串的a的奇偶性，再减去对应的a‘的奇偶性位置最小值就可以得到最长的字符串了。同样的道理，我们只需要把情况扩展到5个元音，也就是有2的5次方个最小值位置要记录，所以我们只需要建立一个数组来记录这些最小值，然后不断更新字符串的奇偶性即可。
最后在遍历过程中不断更新最大值。把上面的思路用代码表现出来，就可以了。

解答

import kotlin.math.max

class Solution {
    fun findTheLongestSubstring(s: String): Int {
        var num = 0 //记录最长符合条件字符串的最大值
        var status = 0 // 记录当前状态
        // 记录每一种状态的位置最小值
        val array = Array(1 shl 5) {-1} 
        // 0肯定符合偶数的条件，所以定为0，-1表示还没找到位置最小值
        array[0] = 0
        //遍历字符串并更新状态
        for (i in s.indices){
            when(s[i]){
                'a' -> status = status xor 1
                'e' -> status = status xor (1 shl 1)
                'i' -> status = status xor (1 shl 2)
                'o' -> status = status xor (1 shl 3)
                'u' -> status = status xor (1 shl 4)
            }
            //如果前面已经有对应的状态出现，那么就减去得到长度，如果没有就把当前位置放上去。记得加1，因为位置是从0开始
            if (array[status]>=0){
                num = max(num,i+1-array[status])
            }else{
                array[status] = i+1
            }
        }
        //最后返回最大长度
        return num
    }
}