1371. 每個元音包含偶數次的最長子字符串

哈希表

題目要求母音都出現偶數次的最長子字串長度。

我們可以用前綴和去紀錄當前的狀態，00000 就代表 aeiou 的出現次數都是偶數，也是最初的狀態。
舉例來說，現在的字串是 $aeae$，那麼前綴合的變化會是 10000, 11000, 01000, 00000。
每一個位數都 % 2，只要餘 0，就代表偶數。

程式碼

class Solution {
public:
    int findTheLongestSubstring(string s) {
        // 在子字串中都出現了兩次
        int res = 0;
        unordered_map<vector<bool>, int> pos;
        vector<bool> alpha(5, false);
        pos[alpha] = -1; // 一開始都出現偶數次
        for(int i = 0; i < s.length(); ++i) {
            if(s[i] == 'a') alpha[0] = !alpha[0];
            else if(s[i] == 'e') alpha[1] = !alpha[1];
            else if(s[i] == 'i') alpha[2] = !alpha[2];
            else if(s[i] == 'o') alpha[3] = !alpha[3];
            else if(s[i] == 'u') alpha[4] = !alpha[4];
            if(pos.contains(alpha)) { // 出現過這個狀態，兩個狀態之間的母音數量都是偶數
                res = max(res, i - pos[alpha]);
            }
            else { // 第一次出現這個狀態。ㄋ
                pos[alpha] = i;
            }
        }
        return res;
    }
};

位運算

因為狀態只會有 00000 ~ 11111，只需要一個位元，就能用來表示母音的出現次數是偶數還是奇數
當獲取到母音時，將對應的位元翻轉。

程式碼

class Solution {
public:
    int findTheLongestSubstring(string s) {
        // 在子字串中都出現了兩次
        int res = 0;
        int pos[32];
        fill(pos, pos + 32, -2); // 需要設定為不會出現的數字，這裡用 -2。
        int alpha = 0;
        pos[0] = -1; // 一開始都出現偶數次
        for(int i = 0; i < s.length(); ++i) { 
            if(s[i] == 'a') alpha ^= 1;
            else if(s[i] == 'e') alpha ^= 2;
            else if(s[i] == 'i') alpha ^= 4;
            else if(s[i] == 'o') alpha ^= 8;
            else if(s[i] == 'u') alpha ^= 16;
            if(pos[alpha] != -2) {
                res = max(res, i - pos[alpha]);
            }
            else {
                pos[alpha] = i;
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$