Maximum Number of Vowel Letters in a Substring
題目描述
給定字串 s 和整數 k，回傳長度為 k 的子字串中最多包含多少個母音字母。
輸入：s = "abciiidef", k = 3
輸出：3（子字串 "iii"）
輸入：s = "aeiou", k = 2
輸出：2
輸入：s = "leetcode", k = 3
輸出：2（子字串 "lee" 或 "eet"）
解題思路
初始窗口
計算前 k 個字元中母音的數量，例如 s=abciiidef, k=3 → [abc] 含 1 個母音(a)
滑動：加入新字元
窗口右邊界向右移一格，新進來的字元 s[i] 如果是母音(aeiou) 就 count++
滑動：移除舊字元
窗口左邊界離開的字元 s[i-k] 如果是母音就 count--，保持窗口大小固定為 k
更新最大值
每次滑動後 maxVowels = max(maxVowels, count)，遍歷完回傳 maxVowels
程式碼
C#
public class Solution {
public int MaxVowels(string s, int k) {
var vowels = new HashSet<char>("aeiou");
int count = 0;
// 初始窗口
for (int i = 0; i < k; i++)
if (vowels.Contains(s[i])) count++;
int maxCount = count;
// 滑動窗口
for (int i = k; i < s.Length; i++) {
if (vowels.Contains(s[i])) count++;
if (vowels.Contains(s[i - k])) count--;
maxCount = Math.Max(maxCount, count);
}
return maxCount;
}
}TypeScript
function maxVowels(s: string, k: number): number {
const vowels = new Set("aeiou");
let count = 0;
for (let i = 0; i < k; i++)
if (vowels.has(s[i])) count++;
let maxCount = count;
for (let i = k; i < s.length; i++) {
if (vowels.has(s[i])) count++;
if (vowels.has(s[i - k])) count--;
maxCount = Math.max(maxCount, count);
}
return maxCount;
}Python
def maxVowels(s: str, k: int) -> int:
vowels = set("aeiou")
count = sum(1 for c in s[:k] if c in vowels)
max_count = count
for i in range(k, len(s)):
count += (s[i] in vowels) - (s[i - k] in vowels)
max_count = max(max_count, count)
return max_count複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(1) |
- Time：初始化窗口 O(k) + 滑動 O(n-k) = O(n)，每步只做常數次 Set 查找和加減
- Space：母音集合固定 5 個字元，count 和 maxCount 為常數，不隨 n 增長
邊界情況
- k 等於字串長度：只有一個窗口，初始化計算的母音數就是答案，滑動迴圈不會執行
- 字串全是母音（如
"aeiou"）：初始窗口就達到 k，maxCount = k，可以在第一步就提前回傳 - 字串沒有母音（如
"bcdfg"）：每個窗口的母音數都是 0，maxCount 始終為 0 - k 等於 1：窗口大小為 1，問題退化為「字串中是否包含母音」，有母音則答案 1，否則 0
圖解
圖表展示了窗口滑動過程：初始窗口 [abc] 含 1 個母音(a)，滑到 [cii] 時變成 2 個，最終 [iii] 達到最大值 3。
每次滑動只需加上新進字元、減去離開字元，不需重新計算整個窗口。
進階觀點
💡面試追問
Q: 跟 Maximum Average Subarray 的差別？ A: 本質相同，都是固定大小滑動窗口。差別只在「窗口值」的定義：Maximum Average 累加數字求平均，本題計算滿足條件（是母音）的元素個數。框架完全一樣。
Q: 如果窗口大小不固定怎麼辦？ A: 改用可變大小的滑動窗口，需要額外的 left 指標和收縮條件。例如 Longest Substring Without Repeating Characters 就是窗口在違反條件時收縮左邊。
Q: 有沒有提前終止的優化？
A: 如果 maxCount == k，可以直接回傳，因為窗口裡全是母音，不可能更好。這在母音密集的字串中能節省不少遍歷。
Q: 用 HashSet 判斷母音 vs 直接用字元比較，哪個更好？
A: HashSet 查找是 O(1) 但有常數開銷（hash 計算）。直接比較 5 個字元（c == 'a' || c == 'e' || ...）在實務中更快，因為分支預測器對少量比較很高效。面試中兩者都可以。
理解測驗
🤔 Python 中 (s[i] in vowels) - (s[i-k] in vowels) 這個寫法為什麼能用？
🤔 如果 s 全部是子音（沒有母音），結果是什麼？