Watch 10 video solutions for Maximum Number of Vowels in a Substring of Given Length, a medium level problem involving String, Sliding Window. This walkthrough by NeetCodeIO has 20,972 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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'.
Example 1:
Input: s = "abciiidef", k = 3 Output: 3 Explanation: The substring "iii" contains 3 vowel letters.
Example 2:
Input: s = "aeiou", k = 2 Output: 2 Explanation: Any substring of length 2 contains 2 vowels.
Example 3:
Input: s = "leetcode", k = 3 Output: 2 Explanation: "lee", "eet" and "ode" contain 2 vowels.
Constraints:
1 <= s.length <= 105s consists of lowercase English letters.1 <= k <= s.lengthProblem Overview: Given a string s and an integer k, find the maximum number of vowels present in any substring of length k. You must examine all substrings of fixed size k and return the highest vowel count among them.
Approach 1: Sliding Window (O(n) time, O(1) space)
The key observation is that every candidate substring has the same length k. Instead of recomputing the vowel count for every substring from scratch, maintain a running count while moving a window across the string. Start by counting vowels in the first k characters. Then iterate through the string one character at a time: remove the effect of the character leaving the window and add the effect of the character entering it. This constant-time update makes each step efficient. Track the maximum count seen so far while iterating.
This approach processes each character once, resulting in O(n) time complexity and O(1) space since only a few counters are stored. The technique is a classic example of the sliding window pattern used in many string problems involving fixed-size subarrays or substrings.
Approach 2: Prefix Sum + Binary Search Style Range Query (O(n) preprocessing, O(1) query, O(n) space)
Another method precomputes a prefix array where prefix[i] stores the number of vowels in the first i characters of the string. With this structure, the number of vowels in any substring [l, r] can be calculated instantly as prefix[r + 1] - prefix[l]. Iterate through all starting positions of length k substrings and compute the vowel count using the prefix array. Each query becomes constant time after preprocessing.
This method uses O(n) extra space for the prefix array but keeps the logic straightforward and useful when you need repeated substring range queries. The technique is based on the prefix sum pattern often used for fast range calculations.
Recommended for interviews: The sliding window approach is the expected solution. Interviewers want to see that you recognize fixed-size substring problems and apply the sliding window pattern to avoid redundant computation. A brute-force solution that recalculates each substring demonstrates basic understanding, but the sliding window shows algorithmic maturity and reduces time complexity from O(n * k) to O(n).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window | O(n) | O(1) | Best general solution for fixed-length substring problems and expected interview answer |
| Prefix Sum | O(n) | O(n) | Useful when many substring range queries are required after preprocessing |