1456. Maximum Number of Vowels in a Substring of Given Length
Problem Description
The problem asks for the maximum number of vowel letters that can be found in any substring of a given string s
with a fixed length k
. The vowels in English are defined as 'a', 'e', 'i', 'o', and 'u'. A substring is any continuous sequence of characters in the string. For example, if s
is "banana" and k
is 3, we need to find the substring of length 3 that has the most vowels. This problem is solved by checking each possible substring of length k
and finding the one with the most vowels.
Intuition
To solve this problem efficiently, we use a technique called the sliding window algorithm. The idea is to maintain a window of size k
that slides over the string s
from the beginning to the end. This window keeps track of the number of vowels in the current substring of length k
.
Here are the steps to implement this approach:
- Initialize a set of vowels for quick look-up.
- Start by counting the number of vowels in the first substring of length
k
. - As you slide the window by one position to the right, add one to the count if the incoming character is a vowel and subtract one if the outgoing character is a vowel.
- Update the maximum number of vowels found so far.
This way, you don't have to check each substring from scratch; you just update the count based on the characters that are entering and exiting the window as it slides. This makes the solution very efficient because each character in s
is processed exactly once.
Learn more about Sliding Window patterns.
Solution Approach
The implementation uses the sliding window technique alongside a set for fast vowel checking, and simple arithmetic operations for counting. Let's break down the steps and logic used in the solution:
-
Create a Set of Vowels: First, a set containing the vowels
'aeiou'
is created for O(1) lookup times. This is done to quickly determine if a character is a vowel.vowels = set('aeiou')
-
Count Vowels in the First Window: Next, the number of vowels in the first window (the first
k
characters) of the string is counted. This forms our initial maximum.t = sum(c in vowels for c in s[:k]) ans = t
-
Slide the Window: The algorithm then iterates through the string starting from the
k
th character. For each new character that enters the window, we add1
tot
if it's a vowel. Simultaneously, we subtract1
fromt
if the character that is exiting the window (which isi - k
characters behind the current character) is a vowel.for i in range(k, len(s)): t += s[i] in vowels t -= s[i - k] in vowels
-
Update Maximum: After adjusting the count for the new window position, we check if the current count
t
is greater than our recorded maximumans
. If it is, we updateans
to be equal tot
.ans = max(ans, t)
-
Return Result: After sliding through the entire string,
ans
will hold the maximum number of vowels found in any substring of lengthk
. This result is then returned.return ans
The simplicity and efficiency of this solution come from the fact that each character is looked at exactly twice per iteration (once when it enters the window and once when it leaves), leading to an O(n) runtime complexity where n
is the length of the string s
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using the string s = "celebration"
and k = 5
. We are looking for the maximum number of vowels in any substring of length 5.
-
Create a Set of Vowels: We initialize a set containing the vowels for quick look-up.
vowels = set('aeiou')
-
Count Vowels in the First Window: Our first window is 'celeb'. We count the number of vowels in this window.
t = sum(c in vowels for c in "celeb") # t = 2 ('e' and 'e') ans = t # ans = 2
-
Slide the Window: Now we start sliding the window one character at a time to the right and adjust the count
t
.-
Move 1: New window is 'elebr'. We add 1 for 'e' (new) and do not subtract any because 'c' (old) is not a vowel.
t
now becomes3
(from 'e', 'e', 'a'), andans
remains3
because3 > 2
. -
Move 2: New window is 'lebra'. We add 1 for 'a' (new) and subtract 1 for 'e' (old).
t
remains3
(from 'e', 'e', 'a'), andans
remains3
. -
Move 3: New window is 'ebrat'. We add 1 for 'a' (new) and subtract 1 for 'e' (old).
t
remains3
(from 'e', 'e', 'a'), andans
remains3
. -
Move 4: New window is 'brati'. We add 1 for 'i' (new) and do not subtract any because 'l' (old) is not a vowel.
t
now becomes3
(from 'e', 'a', 'i'), andans
remains3
. -
Move 5: New window is 'ratio'. We add 1 for 'o' (new) and subtract 1 for 'b' (old).
t
now becomes3
(from 'a', 'i', 'o'), andans
remains3
. -
Move 6: New window 'ation'. We add 1 for 'a' (new) and subtract 1 for 'r' (old).
t
now becomes3
(from 'a', 'i', 'o'), andans
remains3
.
In each move, we adjust
t
and updateans
if necessary:for i in range(5, len(s)): t += s[i] in vowels t -= s[i - 5] in vowels ans = max(ans, t)
-
-
Return Result: After sliding through the entire string
s
, we find thatans = 3
is the maximum number of vowels we can find in any substring of length5
.
The final result for this example is 3
, which means the maximum number of vowels found in any substring of length 5
in the string "celebration" is three.
Solution Implementation
1class Solution:
2 def maxVowels(self, s: str, k: int) -> int:
3 # Define a set containing all vowels for easy access and checking
4 vowels = set('aeiou')
5
6 # Initial count of vowels in the first window of size k
7 current_vowel_count = sum(char in vowels for char in s[:k])
8
9 # Initialize maximum vowels found in a window
10 max_vowel_count = current_vowel_count
11
12 # Slide the window by one character from the kth element to the end
13 for i in range(k, len(s)):
14 # Increase count if the incoming character is a vowel
15 current_vowel_count += s[i] in vowels
16 # Decrease count since we are leaving the character at the start of the window
17 current_vowel_count -= s[i - k] in vowels
18
19 # Update maximum if the current window has more vowels than previous maximum
20 max_vowel_count = max(max_vowel_count, current_vowel_count)
21
22 # Return the maximum number of vowels found in any window of size k
23 return max_vowel_count
24
1class Solution {
2 /**
3 * Calculates the maximum number of vowels in any substring of length k.
4 *
5 * @param s The input string.
6 * @param k The length of the substring.
7 * @return The maximum number of vowels found in any substring of length k.
8 */
9 public int maxVowels(String s, int k) {
10 // Initialize the total vowel count for the first window of size k
11 int totalVowelsInWindow = 0,
12 stringLength = s.length();
13
14 // Count the number of vowels in the initial window of size k
15 for (int i = 0; i < k; ++i) {
16 if (isVowel(s.charAt(i))) {
17 ++totalVowelsInWindow;
18 }
19 }
20
21 // Initialize the answer with the vowel count of the first window
22 int maxVowels = totalVowelsInWindow;
23
24 // Slide the window of size k across the string
25 for (int i = k; i < stringLength; ++i) {
26 // If the newly included character is a vowel, increase the count
27 if (isVowel(s.charAt(i))) {
28 ++totalVowelsInWindow;
29 }
30
31 // If the character that got excluded from the window is a vowel, decrease the count
32 if (isVowel(s.charAt(i - k))) {
33 --totalVowelsInWindow;
34 }
35
36 // Update maxVowels if the current window has more vowels than the previous ones
37 maxVowels = Math.max(maxVowels, totalVowelsInWindow);
38 }
39
40 // Return the maximum number of vowels found
41 return maxVowels;
42 }
43
44 /**
45 * Helper method to check if a character is a vowel.
46 *
47 * @param character The character to be checked.
48 * @return true if the character is a vowel, false otherwise.
49 */
50 private boolean isVowel(char character) {
51 // A character is a vowel if it is one of 'a', 'e', 'i', 'o', or 'u'
52 return character == 'a' ||
53 character == 'e' ||
54 character == 'i' ||
55 character == 'o' ||
56 character == 'u';
57 }
58}
59
1class Solution {
2public:
3 // Function to find the maximum number of vowels in any substring of length k
4 int maxVowels(string s, int k) {
5 int count = 0; // Initialize counter for vowels
6 int maxVowelCount = 0; // This will store the maximum count of vowels found
7 int strLength = s.size(); // Store the length of the string
8
9 // Count the number of vowels in the first window of size k
10 for (int i = 0; i < k; ++i)
11 count += isVowel(s[i]);
12
13 maxVowelCount = count; // Initialize maximum vowel count to be the count from the first window
14
15 // Slide the window by one position to the right each time and update counts
16 for (int i = k; i < strLength; ++i) {
17 count += isVowel(s[i]); // Add a vowel count for new character in the window
18 count -= isVowel(s[i - k]); // Subtract a vowel count for the character that is no longer in the window
19 maxVowelCount = max(maxVowelCount, count); // Update maximum count if current window has more vowels
20 }
21
22 return maxVowelCount; // Return the maximum number of vowels found in any substring of length k
23 }
24
25 // Helper function to check if a character is a vowel
26 bool isVowel(char c) {
27 // A character is a vowel if it is 'a', 'e', 'i', 'o', or 'u'
28 return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
29 }
30};
31
1// Define a function that checks if a character is a vowel
2function isVowel(char: string): boolean {
3 return ['a', 'e', 'i', 'o', 'u'].includes(char.toLowerCase());
4}
5
6// Define a function that finds the maximum number of vowels in a substring of length k within string s
7function maxVowels(s: string, k: number): number {
8 // Initialize total vowel count for the first window of size k
9 let totalVowels = 0;
10 for (let i = 0; i < k; ++i) {
11 if (isVowel(s[i])) {
12 totalVowels++;
13 }
14 }
15
16 // Store the maximum number of vowels found in a window of size k
17 let maxVowelCount = totalVowels;
18
19 // Use a sliding window to count vowels in the remaining windows of size k
20 for (let i = k; i < s.length; ++i) {
21 // Add a vowel count if the newly included character is a vowel
22 if (isVowel(s[i])) {
23 totalVowels++;
24 }
25 // Subtract a vowel count if the excluded character from the left of the window was a vowel
26 if (isVowel(s[i - k])) {
27 totalVowels--;
28 }
29 // Update maximum vowel count if the current window has more vowels
30 maxVowelCount = Math.max(maxVowelCount, totalVowels);
31 }
32
33 // Return the maximum number of vowels found in any window of size k
34 return maxVowelCount;
35}
36
Time and Space Complexity
Time Complexity
The provided code has a time complexity of O(n)
where n
is the length of the string s
. This is because the code iterates over each character of the string exactly once beyond the initial window setup. The initial sum calculation for the first k
characters is O(k)
, and each subsequent step in the loop is constant time O(1)
because it involves adding or subtracting one and checking for the existence of a character in a set, which is also O(1)
. Since k
is at most n
, the entire operation is bounded by O(n)
.
Space Complexity
The space complexity of the code is O(1)
. The space used does not grow with the size of the input string s
. The set of vowels is of constant size (containing 5 elements) and does not change. The variables t
and ans
use a constant amount of space and there are no data structures that grow with the size of the input.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following array represent a max heap?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!