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

本题最关键的地方在于使用 bitmask 压缩状态，以及异或操作的灵活应用。

题目描述

原题链接如下： LeetCode 1371 每个元音包含偶数次的最长子字符串

题目大意

子串的字母必定连续，只关注元音字母的出现次数是否为偶数。另外，0 也是偶数。

输入与输出

字符串字母都是小写的，示例输入为：

1
2
3
4
5
6
7
8

Inout 1:
"eleetminicoworoep"

Input 2:
"leetcodeisgreat"

Input 3:
"bcbcbc"

注意：本题输入数据可能会很大，字符串长度最大为 $5 \times 10^5$，时间复杂度要尽量小。

对应输出为：

1
2
3
4
5
6
7
8

Output 1:
13

Output 2:
5

Output 3:
6

解题思路

对类似连续子串、子数组相关最值等问题，显然可以使用构造前缀和来解决。，定义 pre[i][k] 表示在字符串前 i 个字符中，第 k 个元音字母一共出现的次数。假设我们需要求出 [l,r] 这个区间的子串是否满足条件，那么我们可以用 pre[r][k]-pre[l - 1][k]，得到第 k 个元音字母出现的次数。我们利用前缀和优化了统计子串的时间复杂度，然而枚举所有子串的复杂度仍需要 $O(n^2)$，不足以通过本题，还需要继续进行优化，避免枚举所有子串。其实我们要做的就是快速找到最小的 $j \in [0,i)$，满足 pre[i][k] - pre[j][k]（即每一个元音字母出现的次数）均为偶数，那么以 i 结尾的最长字符串 s[j + 1, i] 长度就是 i - j。 所以，实际上我们只需要维护每个元音字母出现次数的奇偶性即可。但是，5 个元音字母每个需要 2 种状态，如果定义新的类表示会非常复杂，而且本题数据可能会比较大，复杂的数据结构会显著拖慢运行速度。不妨考虑使用 bitmask：用 5 个二进制位表示 5 个元音字母的奇偶性，奇数对应 1，偶数对应 0。这样，我们就把 5 个状态压缩到了 1 个整数数字中，最大就是 31。 不仅如此，二进制和奇偶性对应后，我们还能够使用异或操作求解“前缀和”——偶数个同样的元音字母对应状态位异或结果为 0，奇数个为 1。另外，没有元音字母用 0 表示也能够和 0 时偶数的情况对应。 最后，问题转化为对每个前缀和状态 pre[i]，求最早出现的 $j \in [0,i)$ 使得 pre[j] == pre[i] 成立。我们只需要维护一个长度为 32 的数组，保存每个前缀和状态最早出现时子串的从 0 开始的长度即可。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun findTheLongestSubstring(s: String): Int {
        val lengths = IntArray(1 shl 5) { -1 }
        var re = 0
        var bitmask = 0
        lengths[0] = 0
        for (i in s.indices) {
            bitmask = bitmask xor when (s[i]) {
                'a' -> 1
                'e' -> 2
                'i' -> 4
                'o' -> 8
                'u' -> 16
                else -> 0
            }
            if (lengths[bitmask] == -1) lengths[bitmask] = i + 1
            else re = maxOf(re, i + 1 - lengths[bitmask])
        }
        return re
    }
}