Description
給定字串
s和整數k，回傳長度為k的子字串中，母音字母（a, e, i, o, u）數量的最大值。
Example:
Input: s = “abciiidef”, k = 3 Output: 3（子字串 “iii” 有 3 個母音）
Intuition#
核心思路：固定大小為 k 的滑動視窗，維護視窗內的母音計數，每次移動時更新計數。
- 固定視窗大小的經典題
- 每次右移時：新進入的字元如果是母音就 +1，離開的字元如果是母音就 -1
Approaches#
1: Brute Force#
- 概念: 計算每個長度為 k 的子字串中母音數量
- 時間複雜度:
O(n * k)- 每個子字串掃描 k 個字元 - 空間複雜度:
O(1)
Brute Force 程式碼
class Solution {
fun maxVowels(s: String, k: Int): Int {
val vowels = setOf('a', 'e', 'i', 'o', 'u')
var result = 0
for (i in 0..s.length - k) {
var count = 0
for (j in i until i + k) {
if (s[j] in vowels) count++
}
result = maxOf(result, count)
}
return result
}
}⭐2: Fixed Sliding Window#
- 概念: 維護大小為 k 的視窗，追蹤母音計數，每步 O(1) 更新
- 時間複雜度:
O(n)- 一次遍歷 - 空間複雜度:
O(1)
class Solution {
fun maxVowels(s: String, k: Int): Int {
val vowels = setOf('a', 'e', 'i', 'o', 'u')
var count = 0
var result = 0
for (i in s.indices) {
if (s[i] in vowels) count++
if (i >= k && s[i - k] in vowels) count--
if (i >= k - 1) result = maxOf(result, count)
}
return result
}
}判斷母音用 Set 查表比多個
||條件更清晰、效能相當。
🔑 Takeaways#
- Pattern: 固定大小滑動視窗 + 計數維護
- 關鍵技巧: 每次移動只需 O(1) 更新（加入新字元、移除舊字元），是固定視窗的核心優勢