Coding Interview PatternsMaximum Number of Vowels in a Substring of Given Length
MediumSliding Window
Maximum Number of Vowels in a Substring of Given Length
Explanation & Solution
Description
Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k.
Vowel letters in English are 'a', 'e', 'i', 'o', and 'u'.
Input: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" contains 3 vowel letters.
Constraints
1 <= s.length <= 10^5sconsists of lowercase English letters.1 <= k <= s.length
Approach
Sliding Window pattern
1. Identify Vowels
- Store vowels
{'a', 'e', 'i', 'o', 'u'}in a set for O(1) lookups.
2. Count Vowels in the Initial Window
- Iterate through the first
kcharacters and count how many are vowels. - This count becomes our initial
maxCount.
3. Slide the Window Across the String
- For each new position, the right pointer advances by one:
- If the entering character (at
right) is a vowel, increment the count. - If the leaving character (at
right - k) is a vowel, decrement the count. - After each slide, update
maxCountif the current count is larger.
4. Return the Maximum
- After processing all windows,
maxCountholds the answer.
Key Insight
- This is a fixed-size sliding window problem. Since the window size
knever changes, we maintain a running count of vowels rather than recounting from scratch for every position. Each slide only needs to check two characters: the one entering and the one leaving.
Time
O(n)each character is visited exactly once.Space
O(1)only a few variables and a fixed-size set.Visualization
Input:
[a, b, c, i, i, i, d, e, f], k = 3
—
Press ▶ or use ← → to step through
Left (L)Right (R)WindowDone
8 steps