< Back

1456. Maximum Number of Vowels in a Substring of Given Length

Sliding window problem. We've got a string and a constraint, k, wherein the sliding window can be no
greater than k. To solve this problem we create a set of vowels so we can easily check if a character
is in the set.

Following this, we evaluate the first window up until k, adding characters that are in the vowels set
to our global total. Once that's done, we iterate through the rest of the string starting from k. We
add to our total if the character we're currently inspecting is in the vowel set. We substract from
our total if the s[i-k] character is in the vowel set, maintaining the constraints of the sliding

We maximize this constraint across all subarrays discovered.

The solution is as follows:

  class Solution:
      def maxVowels(self, s: str, k: int) -> int:
          vowels, ans, total = set("aeiou"), 0, 0

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

          ans = total
          for j in range(k, len(s)):
              total += int(s[j] in vowels)
              total -= int(s[j - k] in vowels)
              ans = max(ans, total)

          return ans

_ Time Complexity:

  O(n) - We iterate through the string once.

_ Space Complexity:

  O(1) - We use a set of vowels, but the size of the set is constant.