Given the string s, return the size of the longest substring containing each vowel an even number of times. That is, 'a', 'e', 'i', 'o', and 'u' must appear an even number of times.

Example 1:

Input: s = "eleetminicoworoep"
Output: 13
Explanation: The longest substring is "leetminicowor" which contains two each of the vowels: e, i and o and zero of the vowels: a and u.

Example 2:

Input: s = "leetcodeisgreat"
Output: 5
Explanation: The longest substring is "leetc" which contains two e's.

Example 3:

Input: s = "bcbcbc"
Output: 6
Explanation: In this case, the given string "bcbcbc" is the longest because all vowels: a, e, i, o and u appear zero times.

Constraints:

• 1 <= s.length <= 5 x 10^5
• s contains only lowercase English letters.

這道題說是給了個字符串s，讓找出一個最長子串，使得其中的元音字母出現次數為偶數次。這里的元音字母就是那五個 a，e，i，o，u。這道題的難點還是在于如何統計元音字母的個數，并且判斷他們是否都為偶數，大多數人可能第一時間就會考慮用個 HashMap 來統計元音字母出現的個數，然后再分別判斷是不是偶數個。其實這里我們對具體的個數并不關心，只要知道是不是偶數，實際上每個元音只有奇數和偶數兩種狀態，總共五個元音，則共有 2^5 = 32 種狀態，那么正好可以使用位運算的思想來記錄狀態，五個元音各用一個二進制的位來記錄狀態，0即為偶數，1為奇數，這里a在最低位，其次按順序是 e,i,o,u。則二進制 00000 就表示五個元音全是偶數，00011 就表示元音a和e為奇數，這里每一位對應的十進制數分別為1，2，4，8，16。這樣范圍為 [0, i] 內的子串的元音奇偶數狀態就知道了，同時還要記錄下第一個出現非0狀態的位置，當下次再次出現相同的狀態碼時，比如 [0, j] 范圍內的子串也是相同的狀態，則范圍 [i, j] 內的子串必定元音都是偶數個的，這樣可以快速來更新結果 res。

明白了這點后，可以來寫代碼了，這里的狀態碼用一個整型數 mask 來表示，同時為了更方便的取出每個元音位對應的十進制數，可以用一個 HashMap 來建立映射。然后還需要一個狀態值和下標之間的映射，這里可以用 HashMap，或者一個大小為 32 的數組 mask2idx 就行，因為狀態碼是不會超過32的整型數，初始化值為 -1。然后可以開始遍歷了，將遍歷到的字母到 vowelMap 中取值，如果是元音，就會取到對應的非零值，然后 mask 異或上這個值，此時若 mask 不為0，且當前的 mask 值之前并沒有出現過，即在 mask2idx 中的值是 -1，此時就更新其值為i。然后用 i - mask2idx[mask] 來更新結果 res 即可，參見代碼如下：

class Solution {
public:
    int findTheLongestSubstring(string s) {
        int res = 0, mask = 0, n = s.size();
        unordered_map<char, int> vowelMap{{'a', 1}, {'e', 2}, {'i', 4}, {'o', 8}, {'u', 16}};
        vector<int> mask2idx(32, -1);
        for (int i = 0; i < s.size(); ++i) {
            mask ^= vowelMap[s[i]];
            if (mask != 0 && mask2idx[mask] == -1) {
                mask2idx[mask] = i;
            }
            res = max(res, i - mask2idx[mask]);
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1371

參考資料：

https://leetcode.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/description/

https://leetcode.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/editorial/

https://leetcode.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/solutions/534135/c-java-with-picture/

LeetCode All in One 題目講解匯總(持續更新中...)