題目敘述 1371. Find the Longest Substring Containing Vowels in Even Counts
給定一個字串s，請找出母音字母出現皆為偶數次的最長子字串的長度。
例如"paaoooq"，母音字母出現皆為偶數次的最長子字串paaoo，長度為5。測試範例
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 time
約束條件
Constraints:
1 <= s.length <= 5 x 10^5
字串s的長度介於1~五十萬之間。
scontains only lowercase English letters.
s只會包含小寫英文字母。
演算法 開關模擬 + 二進位狀態機
題目已經指定是母音字元出現偶數次(0, 2, 4, 6, ...2k次 等)的最長子字串。
那麼我們可以用開關配合二進位狀態機來記錄每個母音的出現次數。
a 對應到bit 0 對應到十進位的1。
bit 0 為1時，代表a出現奇數次；bit 0 為0時，代表a出現偶數次。
e 對應到bit 1 對應到十進位的2。
bit 1 為1時，代表e出現奇數次；bit 1 為0時，代表e出現偶數次。
i 對應到bit 2 對應到十進位的4。
bit 2 為1時，代表i出現奇數次；bit 2 為0時，代表i出現偶數次。
o 對應到bit 3 對應到十進位的8。
bit 3 為1時，代表o出現奇數次；bit 3 為0時，代表o出現偶數次。
u 對應到bit 4 對應到十進位的16。
bit 4 為1時，代表u出現奇數次；bit 4 為0時，代表u出現偶數次。
一開始，空字串，母音字元出現0次，每個母音的開關都在OFF狀態。
接著，掃描每個字元，假如是母音，就撥動對應的母音開關一次(OFF->ON或者ON->OFF)。
假如，從index i 到 index j某個狀態曾經出現過兩次，代表中間這段子字串母音字元剛好出現偶數次。接著，取得當下的子字串長度j-1，比較並且更新合法子字串的最大值。
程式碼 開關模擬 + 二進位狀態機
class Solution:
def findTheLongestSubstring(self, s: str) -> int:
# bit mask position
vowel_mask = {'a':1,'e':2,'i':4,'o':8,'u':16}
# key: state
# value: last seen position
last_seen = {0:-1}
# state of vowels
# toggle between odd occurrence and even occurrence
state = 0
# length of valid substring with even occurrence of vowels
length = 0
# Scan each character
for idx, char in enumerate(s):
# update state by corresponding vowel bitmask
if char in vowel_mask:
state ^= vowel_mask[char]
if state not in last_seen:
# update last seen poistion of current state
last_seen[state] = idx
else:
# update length of valid substring with even occurrence of vowels
length = max(length, idx-last_seen[state])
return length
複雜度分析
時間複雜度: O(n)
線性掃描每個字元一次，字串總長度為O(n)
空間複雜度: O(1)
最多要維護O(2^5) = O(32) =O(1)個狀態，所需空間為常數級別。
Reference
[1] Find the Longest Substring Containing Vowels in Even Counts - LeetCode
