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.
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'; }}Video 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.