LeetCode 1371 每个元音包含偶数次的最长子字符串
本题最关键的地方在于使用 bitmask 压缩状态,以及异或操作的灵活应用。
题目描述
原题链接如下: LeetCode 1371 每个元音包含偶数次的最长子字符串
题目大意
子串的字母必定连续,只关注元音字母的出现次数是否为偶数。另外,0 也是偶数。
输入与输出
字符串字母都是小写的,示例输入为:
|
|
注意:本题输入数据可能会很大,字符串长度最大为 $5 \times 10^5$,时间复杂度要尽量小。
对应输出为:
|
|
解题思路
对类似连续子串、子数组相关最值等问题,显然可以使用构造前缀和来解决。,定义 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 开始的长度即可。
代码
|
|