題目

1371. Find the Longest Substring Containing Vowels in Even Counts

題意

給定一字串s，求最長子字串長度，使得子字串中的每種母音數量都是偶數個。

方向

用一個真假值陣列儲存索引零到當前元素的母音數量狀態，我是是直接存各母音是否為偶數。
若0~i的母音狀態與0~j的母音狀態相同，則i~j的各母音數數量必為偶數，因為每種母音都要改變兩次狀態才能變回原樣，而兩次即是偶數。

因此這題的關鍵就是狀態的資料結構選擇，以及查找第一次出現相同狀態的索引值。我這裡是用布林陣列，再用布林陣列做為鍵值做哈希表。

實作

class Solution {
public:
    int findTheLongestSubstring(string s) {
        int n = (int)s.length();
        vector<bool> is_even(5, true); // a e i o u
        
 // is_even -> first appear index 
        unordered_map<vector<bool>, int> um;
        // Number of vowels are even at first
        um[is_even] = -1;
        
        int res = 0;
        for(int i = 0; i < n; i++)
            {
            char c = s[i];
            if(c == 'a')
                is_even[0] = !is_even[0];
            if(c == 'e')

                is_even[1] = !is_even[1];
            if(c == 'i')

                is_even[2] = !is_even[2];
            if(c == 'o')

                is_even[3] = !is_even[3];
            if(c == 'u')

                is_even[4] = !is_even[4];
            if(um.find(is_even) != um.end())
                res = max(res, i - um[is_even]);
            else
                um[is_even] = i;
        }
        return res;
        
    }
};         

分析

若字串長度為N
時間複雜度：O(N)
空間複雜度：O(N)

結果