力扣1371.每个元音包含偶数次的最长子字符串
-
状态压缩 + 前缀和
- 用一个二进制的五位数存每种元音字母的出现次数
- 同时记录每种情况第一次出现的下标
-
class Solution {public:int findTheLongestSubstring(string s) {vector<int> pre(32,INT_MAX);pre[0] = -1;int n = s.size();int cur = 0,ans = 0;for(int i=0;i<n;i++){if(s[i] == 'a')cur ^= 1 << 0;else if(s[i] == 'e')cur ^= 1 << 1;else if(s[i] == 'i')cur ^= 1 << 2;else if(s[i] == 'o')cur ^= 1 << 3;else if(s[i] == 'u')cur ^= 1 << 4;if(pre[cur] == INT_MAX) pre[cur] = i;else ans = max(ans,i - pre[cur]);}return ans;}};