1456. Maximum Number of Vowels in a Substring of Given Length
On This Page
Given a string
s and an integer
k, the task is to return the maximum number of vowel letters in any substring of
s with length
Vowel letters in English are ‘a’, ’e’, ‘i’, ‘o’, and ‘u’.
The most straightforward solution to this problem is to take every possible substring of length
k and count the number of vowels in each of them. This can be done using nested loops. The outer loop runs through each character in the string while the inner loop counts the vowels for each substring of length
k. The maximum count is then returned.
However, this naive solution would be computationally expensive, with a time complexity of $O(n*k)$ where n is the length of the string
Hints & Tips
The problem can be efficiently solved using a technique called the sliding window approach.
Approach: Sliding Window
The idea is to use a window of size
k and slide it across the string
s. Instead of counting the number of vowels in the entire window every time, we adjust the count by adding the new character and removing the leftmost character as the window slides.
This way, the number of operations is reduced to just two for every slide, making it a more efficient solution.
- Initialize a counter for the number of vowels and a
max_vowelsvariable to keep track of the maximum number of vowels seen.
- Traverse through the first
kcharacters of the string, increasing the counter for each vowel seen.
max_vowelsto the value of the counter.
- Start sliding the window from the
kth character. For every new character:
- If it’s a vowel, increase the counter.
- Check the leftmost character of the previous window (i.e.,
s[i - k]). If it’s a vowel, decrease the counter.
max_vowelsif the counter is greater than its current value.
def maxVowels(s, k): vowels = set(['a', 'e', 'i', 'o', 'u']) count = sum(1 for char in s[:k] if char in vowels) max_vowels = count for i in range(k, len(s)): # Add the new character to the count if it's a vowel count += s[i] in vowels # Remove the leftmost character of the previous window from the count if it's a vowel count -= s[i - k] in vowels max_vowels = max(max_vowels, count) return max_vowels