Maximum Number of Vowels in a Substring of Given Length - Solution & Explanation
Problem Statement
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 <= 105sconsists of lowercase English letters.1 <= k <= s.length
Approach Overview
Problem 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 1: Sliding Window Approach
This approach uses the sliding window technique to efficiently find the maximum number of vowels in any substring of length k.
We first calculate the number of vowels in the initial window of length k. Then, for each subsequent character, we slide the window by one character to the right: we remove the character that goes out of the window and add the one that comes into the window, updating our vowel count accordingly.
This ensures that we examine each character in the string only once, leading to an O(n) time complexity.
The solution involves converting the character check into a vowel helper function to identify vowels. We initiate a loop through the first k characters to initialize our vowel count, then iterate over the remainder of the string, adjusting our count as we move the window along. The result is the maximum count found in any window. Utilizing helper functions helps improve code readability.
Complexity
Time Complexity: O(n), where n is the length of the string. We iterate through the string with a constant number of operations for each character.
Space Complexity: O(1), as we use a fixed amount of extra space.
Approach 2: Prefix Sum and Binary Search Approach
Another way to tackle this problem is to use a combination of prefix sums and binary search to precompute regions of vowels.
First, we establish a prefix sum array that accumulates the number of vowels encountered at each character index in the string. Then, we use a binary search within this prefix sum to efficiently find the maximum number of vowels in any moving window of length k.
This approach is more complex and is generally less optimal than the sliding window approach but provides an alternative methodology.
The C solution creates a prefix sum array to accumulate the number of vowels found up to each point in the string. Using this prefix sum, the maximum number of vowels in any contiguous substring of length k can be determined by calculating the difference between pairs of prefix sums separated by k indices.
Complexity
Time Complexity: O(n), for prefix sum construction and analysis.
Space Complexity: O(n), for the prefix sum array.
Approach 3: Sliding Window
First, we count the number of vowels in the first k characters, denoted as cnt, and initialize the answer ans as cnt.
Then we start traversing the string from k. For each iteration, we add the current character to the window. If the current character is a vowel, we increment cnt. We remove the first character from the window. If the removed character is a vowel, we decrement cnt. Then, we update the answer ans = max(ans, cnt).
After the traversal, we return the answer.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n), where n is the length of the string. We iterate through the string with a constant number of operations for each character. |
| Prefix Sum and Binary Search Approach | Time Complexity: O(n), for prefix sum construction and analysis. |
| Sliding Window | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Maximum Number of Vowels in a Substring of Given Length - Leetcode 1456 - Python • NeetCodeIO • 21,763 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Number of Vowels in a Substring of Given Length easy or hard?
Maximum Number of Vowels in a Substring of Given Length Python/Java solution
How to solve Maximum Number of Vowels in a Substring of Given Length in O(n)?
What is the best approach for Maximum Number of Vowels in a Substring of Given Length?
Is Maximum Number of Vowels in a Substring of Given Length asked at Google/Amazon/Meta?
What data structure is used in Maximum Number of Vowels in a Substring of Given Length?
What is the time complexity of Maximum Number of Vowels in a Substring of Given Length?
Ready to solve this problem?
Practice Maximum Number of Vowels in a Substring of Given Length with our built-in code editor and test cases.
Practice on FleetCode