Title

給你一個字符串 s ，請你返回滿足以下條件的最長子字符串的長度：每個元音字母，即 ‘a’，‘e’，‘i’，‘o’，‘u’ ，在子字符串中都恰好出現了偶數次。

示例 1：

輸入：s = “eleetminicoworoep”
輸出：13
解釋：最長子字符串是 “leetminicowor” ，它包含 e，i，o 各 2 個，以及 0 個 a，u 。

示例 2：

輸入：s = “leetcodeisgreat”
輸出：5
解釋：最長子字符串是 “leetc” ，其中包含 2 個 e 。

示例 3：

輸入：s = “bcbcbc”
輸出：6
解釋：這個示例中，字符串 “bcbcbc” 本身就是最長的，因為所有的元音 a，e，i，o，u 都出現了 0 次。

Solve

前綴和+狀態壓縮

先來考慮最容易想到的暴力方法：枚舉所有子串，遍歷子串中的所有字符，統計元音字母出現的個數，如果符合條件就更新答案，不用想都知道這樣肯定超時。

其實每個子串對應著一個區間，那么有什么方法可以在不重復遍歷子串的前提下，快速求出這個區間里元音字母出現的次數呢？答案就是前綴和，對于一個區間，可以用兩個前綴和的差值，得到其中某個字母出現次數。

對每個元音字母維護一個前綴和，定義pre[i][k]表示在字符串前i個字符中，第k個元音字母一共出現的次數。

假設我們需要求出[l,r]這個區間的子串是否滿足條件，那么我們可以用pre[r][k]-pre[l-1][k]，在O(1)的時間得到第k個元音字母出現的次數，對于每個元音字母都判斷一下其是否出現偶數次即可。

利用前綴和優化了統計子串的時間復雜度，然而枚舉所有子串的復雜度仍需要O(n²)，還是不足以通過本題，還需要繼續進行優化，避免枚舉所有子串。

考慮枚舉字符串的每個位置i，計算以它結尾的滿足條件的最長字符串長度。其實我們要做的就是快速找到最小的j∈[0,i)，滿足pre[i][k]?pre[j][k]均為偶數，那么以i結尾的最長字符串s[j+1,i]長度就是i-j。

但是單單利用前綴和，還是無法找到i和j相關的恒等式。這道題還有一個性質沒有充分利用：目標子串中，每個元音字母都恰好出現了偶數次。

偶數這個條件其實告訴了我們，對于滿足條件的子串，兩個前綴和pre[i][k]和pre[j][k]的奇偶性一定是相同的，因此我們可以對前綴和稍作修改，從維護元音字母出現的次數改作維護元音字母出現次數的奇偶性。

這樣我們只要實時維護每個元音字母出現的奇偶性，那么s[j+1,i]滿足條件當且僅當對于所有的k，pre[i][k]和pre[j][k]的奇偶性都相等，此時我們就可以利用哈希表存儲每一種奇偶性對應最早出現的位置，邊遍歷邊更新答案。

其實到這里就差不多了，但是還可以進一步優化編碼方式，如果直接以每個元音字母出現次數的奇偶性為哈希表中的鍵難免有些冗余，因此可以額外定義一個狀態：

{a: cnta, // a 出現次數的奇偶性e: cnte, // e 出現次數的奇偶性i: cnti, // i 出現次數的奇偶性o: cnto, // o 出現次數的奇偶性u: cntu // u 出現次數的奇偶性 }

將這么一個結構當做哈希表存儲的鍵值，如果題目稍作修改擴大了字符集，那么維護起來可能會比較吃力?？紤]到出現次數的奇偶性無非就兩個值，0代表出現了偶數次，1代表出現了奇數次，我們可以將其壓縮到一個二進制數中，第k位的0或1代表了k個元音字母出現的奇偶性，這樣我們也不需要使用哈希表，直接用一個長度為32的數組來存儲對應狀態出現的最大位置即可。

為什么用 0 表示偶數？1 表示奇數？

因為這里我們打算用異或運算，而異或的性質是：如果對兩個二進制做異或，會對其每一位進行位運算，如果相同則為 0，否則為 1。這和上面的性質非常相似。上面說奇偶性相同則位偶數，否則為奇數。因此很自然地用 0 表示偶數，1 表示奇數會更加方便。

復雜度分析

時間復雜度：O(n)
其中 n 為字符串 s 的長度。我們只需要遍歷一遍字符串即可求得答案，因此時間復雜度為 O(n)。

空間復雜度：O(S)
其中 S 表示元音字母壓縮成一個狀態數的最大值，在本題中 S = 32。我們需要對應 S 大小的空間來存放每個狀態第一次出現的位置，因此需要 O(S) 的空間復雜度。

Code

def findTheLongestSubstring(self, s: str) -> int:mapper = {'a': 1, 'e': 2, 'i': 4, 'o': 8, 'u': 16}seen = {0: -1}res = cur = 0for i in range(len(s)):if s[i] in mapper:cur ^= mapper.get(s[i])if cur in seen:res = max(res, i - seen.get(cur))else:seen[cur] = ireturn res

總結

以上是生活随笔為你收集整理的1371. Find the Longest Substring Containing Vowels in Even Counts的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。