⚡Flashcard Drill➔
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

  1. Fixed-length window: count the vowels in the first k characters.
  2. Slide one character at a time, adding the entering character's vowel status and subtracting the leaving one's.
  3. Track the maximum count.
  4. 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 index i - 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.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems