NeetCode #235LC-1456MediumSliding Window
← Back to All Problems#235 · #1456 · Maximum Number of Vowels in a Substring of Given Length(定长子串中元音的最大数目)
📌 Problem Statement & Constraints
Given a string
s and an integer k, return the maximum number of vowel letters in any substring of s with length exactly k. Constraints: 1 <= s.length <= 10^5, 1 <= k <= s.length; s consists of lowercase English letters.💡 Core Algorithmic Approaches
- Fixed-length window: count the vowels in the first
kcharacters. - Slide one character at a time, adding the entering character's vowel status and subtracting the leaving one's.
- Track the maximum count.
- This is the canonical fixed-window template.
💻 Benchmark Python3 Implementation
class Solution:
def maxVowels(self, s: str, k: int) -> int:
vowels = set("aeiou")
cur = sum(1 for ch in s[:k] if ch in vowels)
best = cur
for i in range(k, len(s)):
if s[i] in vowels:
cur += 1
if s[i - k] in vowels:
cur -= 1 # left the window
best = max(best, cur)
return best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass.
💾 Space Complexity
O(1): a set of five characters.
⚠️ Interview Pitfalls & Follow-ups
- Using a variable-length window: the length is fixed at exactly
k. - Forgetting the eviction: the count would grow unboundedly.
- Evicting
s[i - k + 1]: the character leaving the window is at indexi - k. - Recounting the vowels for each window: O(n * k).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner