Teaching Kids Programming – Maximum Number of Vowels in a Substring of Given Length (Sliding Window Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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 <= 10^5
s consists of lowercase English letters.
1 <= k <= s.length

Maximum Number of Vowels in a Substring of Given Length (Sliding Window Algorithm)

This problem can be solved efficiently using a sliding window technique. The following Python solution implements the sliding window approach. It starts by initializing a set of vowels and a variable win to 0. Then, it iterates over the first k characters of the string and adds the number of vowels in the window. It then initializes the variable ans to win.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = {'a', 'e', 'i', 'o', 'u'}
        win = 0
 
        for i in range(k):
            win += s[i] in vowels
 
        ans = win
 
        for i in range(k, len(s)):
            # int(True) is 1 and int(False) is zero
            win += s[i] in vowels
            win -= s[i - k] in vowels
            ans = max(ans, win)           
 
        return ans

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = {'a', 'e', 'i', 'o', 'u'}
        win = 0

        for i in range(k):
            win += s[i] in vowels

        ans = win

        for i in range(k, len(s)):
            # int(True) is 1 and int(False) is zero
            win += s[i] in vowels
            win -= s[i - k] in vowels
            ans = max(ans, win)           
 
        return ans

Next, the function enters a loop that starts from k and iterates over the remaining characters in the string. In each iteration, it adds the next character to the window and subtracts the character that is k positions behind it from the window. It then checks if the current window has a higher number of vowels than the previous maximum and updates ans accordingly. Finally, it returns ans.

The time complexity of this solution is O(n), where n is the length of the string s. The for loop in lines 6-8 has a time complexity of O(k), where k is the length of the substring. The for loop in lines 10-15 has a time complexity of O(n-k), since it iterates over the remaining characters in the string. Therefore, the total time complexity is O(k) + O(n-k) = O(n).

The space complexity of this solution is O(1), since it uses a constant amount of extra space to store the set of vowels and the variables win and ans.

In conclusion, the given Python solution efficiently solves the Leetcode 1456 problem using a sliding window approach with a time complexity of O(n) and a space complexity of O(1).

Another variant of the Sliding Window Implementation is illustrated in the following Python code:

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = {'a', 'e', 'i', 'o', 'u'}
        win = 0
        ans = 0
 
        for i in range(len(s)):                        
            win += s[i] in vowels
            if i >= k:
                win -= s[i - k] in vowels
            ans = max(ans, win)           
 
        return ans

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = {'a', 'e', 'i', 'o', 'u'}
        win = 0
        ans = 0

        for i in range(len(s)):                        
            win += s[i] in vowels
            if i >= k:
                win -= s[i - k] in vowels
            ans = max(ans, win)           
 
        return ans

We only remove the leftmost character after the first K-1 letters. Therefore, there is no need to deal with the first window as a special case. This implementation has the same time and space complexity.

One important thing to note about this solution is that it assumes that the input string s only contains lowercase letters. If s can contain uppercase letters or non-alphabetic characters, then the code in lines 6-8 should be modified to handle them properly.

Additionally, the solution assumes that k is less than or equal to the length of s. If k is greater than the length of s, then the function should return 0.

It’s worth mentioning that there are other approaches to solving this problem, such as using regular expressions or iterating over all substrings of length k. However, the sliding window technique used in this solution is generally faster and more efficient than these approaches.

Overall, the given Python solution is a clean and efficient implementation of the sliding window approach to solve the Leetcode 1456 problem. It demonstrates how to use this technique to efficiently find the maximum number of vowels in a substring of a given length in a string.

One important thing to note about this solution is that it assumes that the input string s only contains lowercase letters. If s can contain uppercase letters or non-alphabetic characters, then the code in lines 6-8 should be modified to handle them properly.

Additionally, the solution assumes that k is less than or equal to the length of s. If k is greater than the length of s, then the function should return 0.

It’s worth mentioning that there are other approaches to solving this problem, such as using regular expressions or iterating over all substrings of length k. However, the sliding window technique used in this solution is generally faster and more efficient than these approaches.

Overall, the given Python solution is a clean and efficient implementation of the sliding window approach to solve the problem. It demonstrates how to use this technique to efficiently find the maximum number of vowels in a substring of a given length in a string.

–EOF (The Ultimate Computing & Technology Blog) —