[LeetCode] 1456. Maximum Number of Vowels in a Substring of Given Length

1. Question

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.

2. Thoughts

Using the sliding window algorithm,
simply:
1) get the first k substring and get all vowels
2) from next substring, minus the first char(if it is vowel), and plus the last char(if it is vowel)

For comparison, use set as comparing if it is in set is known to be o(N).

3. Tips learned

4. My solution

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        count = maxs = 0
        vowel = set("aeiou")
        isFirstVowel = s[0] in vowel
        for i in range(k):
            if s[i] in vowel:
                maxs += 1
        count = maxs

        for i in range(1, len(s) - k + 1):
            if isFirstVowel:
                count -= 1
            isFirstVowel = s[i] in vowel
            if s[i + k - 1] in vowel:
                count += 1
                maxs = max(maxs, count)

        return maxs

106/106 cases passed (99 ms)
Your runtime beats 97.63 % of python3 submissions
Your memory usage beats 95.11 % of python3 submissions (17 MB)

5. AI Solution and Improvements

Your current solution employs a sliding window technique to find the maximum number of vowels in any k-length substring, which is a good approach. The algorithmic complexity is O(n) where n is the length of the string, and this is the best we can do given that we have to examine each character at least once.

However, there are a few improvements that can make your code more Pythonic:

1. Naming: Python usually prefers snake_case over camelCase for variable names.
2. maxs can be initialized directly to count instead of updating twice.
3. Combine initialization loop with main loop by initializing count and max_count to zero and starting the main loop from i = 0.

Here's your refactored code:

class Solution:
    def max_vowels(self, s: str, k: int) -> int:
        count = max_count = 0
        vowels = set("aeiou")
        
        for i in range(len(s)):
            # Remove the left-most element of the last window from count
            if i >= k and s[i - k] in vowels:
                count -= 1
            
            # Add the right-most element of the current window to count
            if s[i] in vowels:
                count += 1
            
            # Update max_count
            if i >= k - 1:
                max_count = max(max_count, count)
        
        return max_count

This code should have the same functionality as your original code but with slight improvements to readability and style.