♈成雙成對 尋找母音字母出現偶數的最長子字串_Leetcode #1371

Emmanuel Ikwuegbu on Unsplash

題目敘述 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~五十萬之間。

• s contains 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