包含最多母音，長度為k的子字串_Leetcode #1456 精選75題

Alexander Andrews on Unsplash

題目敘述

題目會給定一個字串s，和指定長度k，問我們包含母音的子字串中，母音數量的最大值是多少?

題目的原文敘述

測試範例

Example 1:

Input: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" contains 3 vowel letters.

Example 2:

Input: s = "aeiou", k = 2
Output: 2
Explanation: Any substring of length 2 contains 2 vowels.

Example 3:

Input: s = "leetcode", k = 3
Output: 2
Explanation: "lee", "eet" and "ode" contain 2 vowels.

約束條件

• 1 <= s.length <= 10^5

字串s的長度介於1~10^5之間。

• s consists of lowercase English letters.

字串s只會包含小寫英文字母。

• 1 <= k <= s.length

k值介於1~字串s的長度之間。

演算法

關鍵在於題目的要求是子字串，而不是子序列。

子字串一定要求必須連續。因此，最適合的演算法框架為滑動窗口sliding window。

題目說字串s只會包含小寫英文字母，因此，先建立一個母音集合{a,e,i,o,u}

接著建立一個長度為k的滑動窗口，依序從左向右滑動，計算並且更新包含有最多母音數量的子字串。

程式碼

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        
        vowels = { 'a', 'e', 'i', 'o', 'u' }
        
        substring = s[:k]
        
        vowel_count = sum( 1 for char in substring if char in vowels )
        
        # record for max vowel count in substring
        max_vowel_count = vowel_count
        
        
        # sliding window of size k
        for tail_index in range(k, len(s)):
            
            head_index = tail_index - k
            head_char, tail_char = s[head_index], s[tail_index]
            
            if head_char in vowels:
                vowel_count -= 1
                
            if tail_char in vowels:
                vowel_count += 1
                
            max_vowel_count = max( max_vowel_count, vowel_count)
            
        
        return max_vowel_count