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

# 1371.每個元音包含偶數次的最長子字符串 # 題目地址（1371. 每個元音包含偶數次的最長子字符串） <https://leetcode-cn.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/> ## 題目描述 ``` <pre class="calibre18">``` 給你一個字符串 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 次。提示： 1 <= s.length <= 5 x 10^5 s 只包含小寫英文字母。 ``` ``` ## 前置知識 - 前綴和 - 狀態壓縮 ## 暴力法 + 剪枝 ## 公司 - 暫無 ### 思路首先拿到這道題的時候，我想到第一反應是滑動窗口行不行。但是很快這個想法就被我否定了，因為滑動窗口（這里是可變滑動窗口）我們需要擴張和收縮窗口大小，而這里不那么容易。因為題目要求的是奇偶性，而不是類似“元音出現最多的子串”等。突然一下子沒了思路。那就試試暴力法吧。暴力法的思路比較樸素和直觀。那就是`雙層循環找到所有子串，然后對于每一個子串，統計元音個數，如果子串的元音個數都是偶數，則更新答案，最后返回最大的滿足條件的子串長度即可`。這里我用了一個小的 trick。枚舉所有子串的時候，我是從最長的子串開始枚舉的，這樣我找到一個滿足條件的直接返回就行了（early return），不必維護最大值。`這樣不僅減少了代碼量，還提高了效率。` ### 代碼代碼支持：Python3 Python3 Code: ``` <pre class="calibre18">``` class Solution: def findTheLongestSubstring(self, s: str) -> int: for i in range(len(s), 0, -1): for j in range(len(s) - i + 1): sub = s[j:j + i] has_odd_vowel = False for vowel in ['a', 'e', 'i', 'o', 'u']: if sub.count(vowel) % 2 != 0: has_odd_vowel = True break if not has_odd_vowel: return i return 0 ``` ``` **復雜度分析** - 時間復雜度：雙層循環找出所有子串的復雜度是O(n2)O(n^2)O(n2)，統計元音個數復雜度也是O(n)O(n)O(n)，因此這種算法的時間復雜度為O(n3)O(n^3)O(n3)。 - 空間復雜度：O(1)O(1)O(1) ## 前綴和 + 剪枝 ### 思路上面思路中`對于每一個子串，統計元音個數`，我們仔細觀察的話，會發現有很多重復的統計。那么優化這部分的內容就可以獲得更好的效率。對于這種連續的數字問題，這里我們考慮使用[前綴和](https://oi-wiki.org/basic/prefix-sum/)來優化。經過這種空間換時間的策略之后，我們的時間復雜度會降低到O(n2)O(n ^ 2)O(n2)，但是相應空間復雜度會上升到O(n)O(n)O(n)，這種取舍在很多情況下是值得的。 ### 代碼代碼支持：Python3，Java Python3 Code: ``` <pre class="calibre18">``` class Solution: i_mapper = { "a": 0, "e": 1, "i": 2, "o": 3, "u": 4 } def check(self, s, pre, l, r): for i in range(5): if s[l] in self.i_mapper and i == self.i_mapper[s[l]]: cnt = 1 else: cnt = 0 if (pre[r][i] - pre[l][i] + cnt) % 2 != 0: return False return True def findTheLongestSubstring(self, s: str) -> int: n = len(s) pre = [[0] * 5 for _ in range(n)] # pre for i in range(n): for j in range(5): if s[i] in self.i_mapper and self.i_mapper[s[i]] == j: pre[i][j] = pre[i - 1][j] + 1 else: pre[i][j] = pre[i - 1][j] for i in range(n - 1, -1, -1): for j in range(n - i): if self.check(s, pre, j, i + j): return i + 1 return 0 ``` ``` Java Code： ``` <pre class="calibre18">``` class Solution { public int findTheLongestSubstring(String s) { int len = s.length(); if (len == 0) return 0; int[][] preSum = new int[len][5]; int start = getIndex(s.charAt(0)); if (start != -1) preSum[0][start]++; // preSum for (int i = 1; i < len; i++) { int idx = getIndex(s.charAt(i)); for (int j = 0; j < 5; j++) { if (idx == j) preSum[i][j] = preSum[i - 1][j] + 1; else preSum[i][j] = preSum[i - 1][j]; } } for (int i = len - 1; i >= 0; i--) { for (int j = 0; j < len - i; j++) { if (checkValid(preSum, s, j, i + j)) return i + 1; } } return 0; } public boolean checkValid(int[][] preSum, String s, int left, int right) { int idx = getIndex(s.charAt(left)); for (int i = 0; i < 5; i++) if (((preSum[right][i] - preSum[left][i] + (idx == i ? 1 : 0)) & 1) == 1) return false; return true; } public int getIndex(char ch) { if (ch == 'a') return 0; else if (ch == 'e') return 1; else if (ch == 'i') return 2; else if (ch == 'o') return 3; else if (ch == 'u') return 4; else return -1; } } ``` ``` **復雜度分析** - 時間復雜度：O(n2)O(n^2)O(n2)。 - 空間復雜度：O(n)O(n)O(n) ## 前綴和 + 狀態壓縮 ### 思路前面的前綴和思路，我們通過空間（prefix）換取時間的方式降低了時間復雜度。但是時間復雜度仍然是平方，我們是否可以繼續優化呢？實際上由于我們只關心奇偶性，并不關心每一個元音字母具體出現的次數。因此我們可以使用`是奇數，是偶數`兩個狀態來表示，由于只有兩個狀態，我們考慮使用位運算。我們使用 5 位的二進制來表示以 i 結尾的字符串中包含各個元音的奇偶性，其中 0 表示偶數，1 表示奇數，并且最低位表示 a，然后依次是 e，i，o，u。比如 `10110` 則表示的是包含偶數個 a 和 o，奇數個 e，i，u，我們用變量 `cur` 來表示。為什么用 0 表示偶數？1 表示奇數？回答這個問題，你需要繼續往下看。其實這個解法還用到了一個性質，這個性質是小學數學知識： - 如果兩個數字奇偶性相同，那么其相減一定是偶數。 - 如果兩個數字奇偶性不同，那么其相減一定是奇數。看到這里，我們再來看上面拋出的問題`為什么用 0 表示偶數？1 表示奇數？`。因為這里我們打算用異或運算，而異或的性質是：如果對兩個二進制做異或，會對其每一位進行位運算，如果相同則位 0，否則位 1。這和上面的性質非常相似。上面說`奇偶性相同則位偶數，否則為奇數`。因此很自然地`用 0 表示偶數？1 表示奇數`會更加方便。 ### 代碼代碼支持：Python3 Python3 Code: ``` <pre class="calibre18">``` class Solution: def findTheLongestSubstring(self, s: str) -> int: mapper = { "a": 1, "e": 2, "i": 4, "o": 8, "u": 16 } seen = {0: -1} res = cur = 0 for 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] = i return res ``` ``` **復雜度分析** - 時間復雜度：O(n)O(n)O(n)。 - 空間復雜度：O(n)O(n)O(n) ## 關鍵點解析 - 前綴和 - 狀態壓縮 ## 相關題目 - [掌握前綴表達式真的可以為所欲為！](https://lucifer.ren/blog/2020/01/09/1310.xor-queries-of-a-subarray/)