Maximum Number of Vowels in a Substring of Given Length
MedPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward approach is to generate every possible substring of length k, count the number of vowels in each one, and keep track of the maximum count found.
Algorithm
- Initialize a variable
max_vowelsto 0. - Iterate through the string
sfrom indexi= 0 tos.length() - k. - For each
i, consider the substring of lengthkstarting ati. - Initialize a
current_vowelscount to 0 for this substring. - Iterate from
j=itoi + k - 1. - If the character at
s.charAt(j)is a vowel, incrementcurrent_vowels. - After counting vowels for the current substring, update
max_vowels = max(max_vowels, current_vowels). - After the outer loop finishes, return
max_vowels.
Walkthrough
This method involves a nested loop. The outer loop iterates through all possible starting positions of a substring of length k. The inner loop then iterates through each character of that substring to count the vowels.
class Solution { public int maxVowels(String s, int k) { int maxVowels = 0; // Outer loop for all possible start indices of a substring of length k for (int i = 0; i <= s.length() - k; i++) { int currentVowels = 0; // Inner loop to count vowels in the current substring for (int j = i; j < i + k; j++) { if (isVowel(s.charAt(j))) { currentVowels++; } } maxVowels = Math.max(maxVowels, currentVowels); } return maxVowels; } private boolean isVowel(char c) { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; }}While simple, this approach is inefficient because it repeatedly scans overlapping portions of the string.
Complexity
Time
O(N * K), where N is the length of the string `s`. We iterate through `N - K + 1` possible starting positions for the substring. For each substring, we iterate `K` times to count the vowels. This results in a nested loop structure, leading to a time complexity that can be approximated as O(N * K).
Space
O(1). We only use a few variables to store the maximum count and the current count, which does not depend on the input size.
Trade-offs
Pros
Simple to understand and implement.
Cons
Inefficient for large inputs, as it re-calculates the vowel count for overlapping parts of substrings repeatedly.
Will likely result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
A more efficient approach is to use the sliding window technique. We maintain a 'window' of size k and slide it across the string one character at a time. Instead of recounting all vowels in the new window, we update the count by considering only the character that enters the window and the character that leaves it. This avoids redundant work.
Algorithm
- Define a helper function
isVowel(char c)to check for vowels in O(1) time. - Initialize a
current_vowelscount by iterating through the firstkcharacters of the strings. - Initialize
max_vowelswith this initialcurrent_vowelscount. - Iterate through the string from index
i=ktos.length() - 1. This loop represents the sliding of the window. - In each iteration, the window slides one position to the right:
- The character
s.charAt(i - k)leaves the window. If it's a vowel, decrementcurrent_vowels. - The character
s.charAt(i)enters the window. If it's a vowel, incrementcurrent_vowels.
- The character
- Update
max_vowels = max(max_vowels, current_vowels)after each slide. - Return
max_vowels.
Walkthrough
We start by calculating the vowel count for the initial window of the first k characters. This count becomes our initial maximum. Then, we iterate from the k-th character to the end of the string. In each step, we slide the window one position to the right. This is done by:
- Checking if the character leaving the window (at the far left) is a vowel. If so, we decrement our current vowel count.
- Checking if the character entering the window (at the far right) is a vowel. If so, we increment our current vowel count. After each slide, we update our overall maximum vowel count. This process ensures we only perform a single pass through the string.
class Solution { public int maxVowels(String s, int k) { int currentVowels = 0; // 1. Calculate vowels in the first window of size k for (int i = 0; i < k; i++) { if (isVowel(s.charAt(i))) { currentVowels++; } } int maxVowels = currentVowels; // 2. Slide the window across the rest of the string for (int i = k; i < s.length(); i++) { // Subtract the vowel count of the character that is leaving the window if (isVowel(s.charAt(i - k))) { currentVowels--; } // Add the vowel count of the character that is entering the window if (isVowel(s.charAt(i))) { currentVowels++; } // Update the maximum maxVowels = Math.max(maxVowels, currentVowels); } return maxVowels; } private boolean isVowel(char c) { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; }}Complexity
Time
O(N), where N is the length of the string `s`. We perform an initial scan of `K` elements, followed by a single pass through the remaining `N - K` elements. Each step in the sliding window takes constant time. Thus, the total time complexity is O(K + (N - K)) = O(N).
Space
O(1). We only use a constant amount of extra space for variables to store the current and maximum vowel counts.
Trade-offs
Pros
Highly efficient with linear time complexity.
Optimal solution for this problem as it avoids redundant calculations.
Cons
Slightly more complex to conceptualize than the brute-force approach.
Solutions
Solution
class Solution {public int maxVowels(String s, int k) { int t = 0, n = s.length(); for (int i = 0; i < k; ++i) { if (isVowel(s.charAt(i))) { ++t; } } int ans = t; for (int i = k; i < n; ++i) { if (isVowel(s.charAt(i))) { ++t; } if (isVowel(s.charAt(i - k))) { --t; } ans = Math.max(ans, t); } return ans; }private boolean isVowel(char c) { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; }}class Solution {public: int maxVowels(string s, int k) { int t = 0, n = s.size(); for (int i = 0; i < k; ++i) t += isVowel(s[i]); int ans = t; for (int i = k; i < n; ++i) { t += isVowel(s[i]); t -= isVowel(s[i - k]); ans = max(ans, t); } return ans; } bool isVowel(char c) { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; }};class Solution: def maxVowels(self, s: str, k: int) -> int: vowels = set('aeiou') t = sum(c in vowels for c in s[: k]) ans = t for i in range(k, len(s)): t += s[i] in vowels t -= s[i - k] in vowels ans = max(ans, t) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.