Maximum Number of Vowels in a Substring of Given Length

Description

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 each. No substring of length 3 has more than 2 vowels.

Constraints

1 <= s.length <= 10^5
s consists of lowercase English letters
1 <= k <= s.length

Signature

def solution(s: str, k: int) -> int: ...

Complexity

Time: O(n)
Space: O(1)

Hints

Pattern: Sliding window with fixed size k
Approach: Count vowels in first k characters. Slide window: add 1 if new char is vowel, subtract 1 if removed char is vowel. Track maximum.
Complexity: Maintain count of vowels in current window, slide in O(n)

Solutions

Python

def is_vowel(c):
    return c == "a" or c == "e" or c == "i" or c == "o" or c == "u"


def solution(s, k):
    count = 0

    for i in range(k):
        count += int(is_vowel(s[i]))

    result = count

    for i in range(k, len(s)):
        count += int(is_vowel(s[i]))
        count -= int(is_vowel(s[i - k]))
        result = max(result, count)

    return result

    # left = 0
    # result = 0
    # count = 0
    # for right in range(len(s)):
    #     if (
    #         s[right] == "a"
    #         or s[right] == "e"
    #         or s[right] == "i"
    #         or s[right] == "o"
    #         or s[right] == "u"
    #     ):
    #         count += 1
    #
    #     # print("BEFORECHECK", left, right, s[left:right+1], count, result)
    #     while k <= right - left + 1:
    #         result = max(result, count)
    #         if (
    #             s[left] == "a"
    #             or s[left] == "e"
    #             or s[left] == "i"
    #             or s[left] == "o"
    #             or s[left] == "u"
    #         ):
    #             count -= 1
    #         left += 1
    #         # print("CHECK", left, right, s[left:right+1], count, result)
    #
    # return result