从Leetcode 每日一题练习继续讨论：
1371. 每个元音包含偶数次的最长子字符串
1371. Find the Longest Substring Containing Vowels in Even Counts
题解
本题第一步容易想到可以使用"前缀和"记录到每个下标的前缀子字符串中各个元音字母个数的奇偶性. 找最长的包含偶数元音字母的子字符串即寻找两个距离最远的下标, 且以这两个下标结尾的前缀子字符串中各个元音字母个数的奇偶性相同. 此时可以想到可以用数组来保存每个元音字母个数的奇偶性, 这样就需要长度为5的数组, 可以是整型数组也可以是布尔数组(仅有奇或者偶两种状态). 只是在比较任意两个下标对应的前缀子字符串元音奇偶性是否相同时需要遍历这个数组.
有没有更快的方法可以避免遍历数组呢? 可以想到对于奇偶这种二值状态, 仅需要一个二进制位就能表示, 而任意一个整型都包含32个二进制位, 所以用一个整数表示五个元音字母的奇偶状态是完全没问题的. 这里是充分利用每个二进制位能包含的信息. 有一个经典问题, 即1000瓶水里有一瓶是有毒的, 需要多少只老鼠才能试出那瓶有毒的毒药(可怜的鼠鼠)也是相同的思想.
有了这个想法后, 我们可以用一个整数来表示到某个下标的前缀子字符串中元音字母的奇偶性, 只要两个下标处对应的整数相同, 则二者之间的子字符串就满足题目要求. 考虑五个元音字母用二进制表示对应的整数最大为31. 可以直接构造一个长度32的二维数组, 记录每个整数对应的开始下标和当前的最长长度, 如此即可在一遍遍历字符串的同时不断更新该数组, 得到每个整数对应的最长长度, 最后遍历这个二维数组, 找出最长长度中的最长长度即得结果.
代码
class Solution {
public:
int findTheLongestSubstring(string s) {
int rows = 32;
int cols = 2;
int currentmask = 0;
int index = 0;
vector<vector<int>> array(rows, vector<int>(cols, -1));
int max_length = 0;
for (char character : s) {
switch (character) {
case 'a': currentmask ^= 1; break;
case 'e': currentmask ^= 2; break;
case 'i': currentmask ^= 4; break;
case 'o': currentmask ^= 8; break;
case 'u': currentmask ^= 16; break;
}
if (currentmask != 0) {
if (array[currentmask][0] == -1) {
array[currentmask][0] = index;
} else {
array[currentmask][1] = index - array[currentmask][0];
max_length = max(max_length, array[currentmask][1]);
}
} else {
max_length = max(max_length, index + 1);
}
index++;
}
return max_length;
}
};