山僧不解数甲子
一叶落知天下秋
用00000到11111来记录每种不同元音出现的可能性，正好32种。。。理解了会发现没那么难。。。
首先大部分人都能想到：暴力枚举所有的情况，每种对应到子串[left, right]，然后再计算这个子串是否满足元音字母出现的个数都为偶数，这样子的话复杂度O(N^3)。
然后优化就能想到动态规划，可以用dp[i][x]表示元音x在前i个字符中出现的次数，两层循环，如果能够找到这样的i和j，其对五个元音x都满足(dp[i][x] - dp[j][x]) % 2 == 0 ，就记录下这个j - i 。直到找到最长的j - i，这样子复杂度O(N^2)。
实际上动态规划就很接近最优解法了，如果x不是标识某个元音，而是能唯一标识前i个字符中，所有元音出现的奇偶状态，那就只要找到最开始的同一状态，就可以了。
实际上，因为只讨论每个元音出现的次数是奇数还是偶数，完全不需要记录次数，直接01就完事。
于是我们可以用5个字符长度的字符串来记录在前i个字符中，每个元音出现次数是奇数还是偶数。
也就是"00000"表示a,e,i,o,u出现的次数都为偶数，而"11111"则表示出现的次数都为奇数。。。
再比如"10000"则表示a出现的次数为奇数，其他元音字符出现的次数为偶数。
而这个字符串，总共的组合只有32种。
于是可以用哈希表记录每种组合字符串第一次出现的位置，那样下次出现时，就能直接得到目标字符串的长度了。。。
这样子的复杂度是O(N)。
class Solution {
public:
int findTheLongestSubstring(string s) {
string status = "00000";
unordered_map<string, int> bit2index;
bit2index[status] = 0;
int ans = 0;
for (int i = 0; i < s.length(); i++) {
switch (s[i]) {
case 'a':
status[0] = status[0] == '0' ? '1' : '0';
case 'e':
status[1] = status[1] == '0' ? '1' : '0';
case 'i':
status[2] = status[2] == '0' ? '1' : '0';
case 'o':
status[3] = status[3] == '0' ? '1' : '0';
case 'u':
status[4] = status[4] == '0' ? '1' : '0';
}
if (bit2index.count(status)) {
ans = max(ans, i - bit2index[status] + 1);
} else bit2index[status] = i + 1;
}
return ans;
}
};
当然用字符串无论是比较还是计算都比较慢，实际上用一个数字就行了，甚至不用4个字节的整型，一个字节的uint8就行。
缺点就是位运算麻烦。。。。
class Solution {
private:
void bit(uint8_t &status, uint8_t index) {
uint8_t x = 1 << index;
if (status & x)
status &= (~x);
else status |= x;
}
public:
int findTheLongestSubstring(string s) {
uint8_t status = 0;
int *bit2index = new int[32];
memset(bit2index, 0xff, 32 * 4);
bit2index[status] = 0;
int ans = 0;
for (int i = 0; i < s.length(); i++) {
switch (s[i]) {
case 'a':
bit(status, 0);
case 'e':
bit(status, 1);
case 'i':
bit(status, 2);
case 'o':
bit(status, 3);
case 'u':
bit(status, 4);
}
if (bit2index[status] != -1) {
ans = max(ans, i - bit2index[status] + 1);
} else bit2index[status] = i + 1;
}
delete[] bit2index;
return ans;
}
};
