題目敘述
題目會給定一個字串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之間。
sconsists 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
