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

更新於 發佈於 閱讀時間約 1 分鐘

題目敘述 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

留言
avatar-img
留言分享你的想法!
小松鼠-avatar-img
發文者
2024/09/15
林燃(創作小說家)
avatar-img
小松鼠的演算法樂園
95會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/10/06
題目敘述 Rank Transform of an Array 給定一個陣列arr,請根據數字的大小給予序號,序號值介於1~len( set(arr) )之間。 最大的數字給予最大的序號。 次大的數字給予次大的序號。 ...依此類推 最小的數字給予最小的序號1。
Thumbnail
2024/10/06
題目敘述 Rank Transform of an Array 給定一個陣列arr,請根據數字的大小給予序號,序號值介於1~len( set(arr) )之間。 最大的數字給予最大的序號。 次大的數字給予次大的序號。 ...依此類推 最小的數字給予最小的序號1。
Thumbnail
2024/10/01
題目敘述 Check If Array Pairs Are Divisible by k 給定一個長度為偶數的整數陣列arr,和一個整數k 。 我們想把陣列元素兩兩一組組成pair,使得每個pair的總和可以被k整除。 如果做得到,返回True。 如果不行,返回False。
Thumbnail
2024/10/01
題目敘述 Check If Array Pairs Are Divisible by k 給定一個長度為偶數的整數陣列arr,和一個整數k 。 我們想把陣列元素兩兩一組組成pair,使得每個pair的總和可以被k整除。 如果做得到,返回True。 如果不行,返回False。
Thumbnail
2024/09/29
My Calendar II 給定一個行事曆的class定義和行程安排的介面。 請完成下列function 1.建構子MyCalendarTwo() 2.boolean book(int start, int end) 在行事曆加入一項新行程,起始時間為start, 結束時間為end。
Thumbnail
2024/09/29
My Calendar II 給定一個行事曆的class定義和行程安排的介面。 請完成下列function 1.建構子MyCalendarTwo() 2.boolean book(int start, int end) 在行事曆加入一項新行程,起始時間為start, 結束時間為end。
Thumbnail
看更多
你可能也想看
Thumbnail
「欸!這是在哪裡買的?求連結 🥺」 誰叫你太有品味,一發就讓大家跟著剁手手? 讓你回購再回購的生活好物,是時候該介紹出場了吧! 「開箱你的美好生活」現正召喚各路好物的開箱使者 🤩
Thumbnail
「欸!這是在哪裡買的?求連結 🥺」 誰叫你太有品味,一發就讓大家跟著剁手手? 讓你回購再回購的生活好物,是時候該介紹出場了吧! 「開箱你的美好生活」現正召喚各路好物的開箱使者 🤩
Thumbnail
1371. Find the Longest Substring Containing Vowels in Even Counts 給定一個字串s,請找出母音字母出現皆為偶數次的最長子字串的長度。 例如"paaoooq",母音字母出現皆為偶數次的最長子字串paaoo,長度為5。
Thumbnail
1371. Find the Longest Substring Containing Vowels in Even Counts 給定一個字串s,請找出母音字母出現皆為偶數次的最長子字串的長度。 例如"paaoooq",母音字母出現皆為偶數次的最長子字串paaoo,長度為5。
Thumbnail
題目敘述 題目會給定一個字串s,和指定長度k,問我們包含母音的子字串中,母音數量的最大值是多少? 題目的原文敘述 測試範例 Example 1: Input: s = "abciiidef", k = 3 Output: 3 Explanation: The substring "iii
Thumbnail
題目敘述 題目會給定一個字串s,和指定長度k,問我們包含母音的子字串中,母音數量的最大值是多少? 題目的原文敘述 測試範例 Example 1: Input: s = "abciiidef", k = 3 Output: 3 Explanation: The substring "iii
Thumbnail
題目敘述 題目會給定我們一個字串s,要求我們反轉字串s中所有母音字元的順序,並且以字串的形式輸出。 註: 母音字元為a, e, i, o, u 或者 A, E, I, O, U 題目的原文敘述 測試範例 Example 1: Input: s = "hello" Output: "ho
Thumbnail
題目敘述 題目會給定我們一個字串s,要求我們反轉字串s中所有母音字元的順序,並且以字串的形式輸出。 註: 母音字元為a, e, i, o, u 或者 A, E, I, O, U 題目的原文敘述 測試範例 Example 1: Input: s = "hello" Output: "ho
Thumbnail
題目敘述 題目會給我們一個輸入字串s,題目還保證字串s的長度一定是偶數。 要求我們判定字串s的前半部和後半部是否相似? 在本題中,兩個字串相似的定義為兩個字串都擁有相同的母音英文字母: 註: 母音英文字母為a, e, i, o, u, A, E, I, O, U 題目的原文敘述 測試
Thumbnail
題目敘述 題目會給我們一個輸入字串s,題目還保證字串s的長度一定是偶數。 要求我們判定字串s的前半部和後半部是否相似? 在本題中,兩個字串相似的定義為兩個字串都擁有相同的母音英文字母: 註: 母音英文字母為a, e, i, o, u, A, E, I, O, U 題目的原文敘述 測試
Thumbnail
題目會給我們一個字串s,內容都是由英文小寫字母組成,要求我們計算長度為3的回文子序列有多少個? 舉例,aba者種形式的序列,就是長度為3的回文序列。
Thumbnail
題目會給我們一個字串s,內容都是由英文小寫字母組成,要求我們計算長度為3的回文子序列有多少個? 舉例,aba者種形式的序列,就是長度為3的回文序列。
Thumbnail
題目會給定我們一個字串s,要求我們計算出同質子字串有幾個? 同質子字串的定義就是子字串內部的字元都相同,例如a, aa, aaa, ... 等等這些就是同質子字串。
Thumbnail
題目會給定我們一個字串s,要求我們計算出同質子字串有幾個? 同質子字串的定義就是子字串內部的字元都相同,例如a, aa, aaa, ... 等等這些就是同質子字串。
Thumbnail
題目會給定一組規則,要求我們計算給定長度下的母音直線排列有幾種?
Thumbnail
題目會給定一組規則,要求我們計算給定長度下的母音直線排列有幾種?
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News