Problem Description

Given a string s and an integer k, your task is to find the maximum number of vowels that appear in any substring of s with length k.

A substring is a contiguous sequence of characters within the string. Vowels are the characters 'a', 'e', 'i', 'o', and 'u'.

Constraints:

• 1 ≤ s.length ≤ 10^5
• 1 ≤ k ≤ s.length
• s consists of lowercase English letters.

Thought Process

The most direct way to solve this problem is to look at every possible substring of length k in s and count how many vowels each contains, keeping track of the maximum.

However, this brute-force approach is inefficient for large strings since it would involve examining a huge number of substrings and repeatedly counting vowels.

To optimize, we can use the sliding window technique. Instead of starting from scratch for every substring, we maintain a window of size k and update the vowel count efficiently as the window slides by one character at a time. This way, we only need to check the character leaving and the one entering the window, making the process much faster.

Solution Approach

Let's break down the optimized algorithm step-by-step:

1. Identify vowels: Create a set or function to check if a character is a vowel.
2. Initialize window: Count the number of vowels in the first k characters of s. This is our initial window.
3. Slide the window: For each subsequent character in s (from index k onward):
   • Subtract one from the vowel count if the character leaving the window (at index i-k) is a vowel.
   • Add one to the vowel count if the character entering the window (at index i) is a vowel.
   • Update the maximum vowel count seen so far.
4. Return the answer: After processing the entire string, return the maximum vowel count found.

This approach ensures each character is processed only twice (once entering, once leaving the window), resulting in a highly efficient solution.

Example Walkthrough

Consider s = "abciiidef" and k = 3.

Let's walk through each step:

• Initial window ("abc"): Contains 'a', which is a vowel. So, vowel count = 1.
• Slide window by 1 ("bci"): 'a' leaves, 'i' enters. 'a' is a vowel, so subtract 1. 'i' is a vowel, so add 1. New count = 1.
• Next window ("cii"): 'b' leaves (not a vowel), 'i' enters (vowel). Add 1. New count = 2.
• Next window ("iii"): 'c' leaves (not a vowel), 'i' enters (vowel). Add 1. New count = 3. This is the maximum so far.
• Next window ("iid"): 'i' leaves (vowel), 'd' enters (not a vowel). Subtract 1. New count = 2.
• Next window ("ide"): 'i' leaves (vowel), 'e' enters (vowel). No net change. Count = 2.
• Next window ("def"): 'i' leaves (vowel), 'f' enters (not a vowel). Subtract 1. Count = 1.

The maximum number of vowels in any substring of length 3 is 3.

Time and Space Complexity

Brute-force approach:

• Time Complexity: O(nk), where n is the length of s. For each of the n-k+1 substrings, we count vowels in k characters.
• Space Complexity: O(1) (ignoring input and output), since we only need counters.

• Time Complexity: O(n), since we process each character a constant number of times (entering and leaving the window).
• Space Complexity: O(1), as we only need a few counters and a vowel set.

The optimized solution is much more efficient, especially for large strings.

Summary

To solve the problem of finding the maximum number of vowels in any substring of a given length, we used the sliding window technique to efficiently update our vowel count as we move through the string. This avoids redundant checks and ensures optimal performance. The key insight was realizing that the change between adjacent windows is minimal, allowing us to update our count in constant time per step. This makes the solution both elegant and highly efficient.

Code Implementation

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = set('aeiou')
        count = 0
        max_count = 0

        # Count vowels in the first window
        for i in range(k):
            if s[i] in vowels:
                count += 1
        max_count = count

        # Slide the window
        for i in range(k, len(s)):
            if s[i - k] in vowels:
                count -= 1
            if s[i] in vowels:
                count += 1
            max_count = max(max_count, count)

        return max_count
      

class Solution {
public:
    int maxVowels(string s, int k) {
        auto isVowel = [](char c) {
            return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
        };
        int count = 0, max_count = 0;
        for (int i = 0; i < k; ++i) {
            if (isVowel(s[i])) ++count;
        }
        max_count = count;
        for (int i = k; i < s.size(); ++i) {
            if (isVowel(s[i - k])) --count;
            if (isVowel(s[i])) ++count;
            if (count > max_count) max_count = count;
        }
        return max_count;
    }
};
      

class Solution {
    public int maxVowels(String s, int k) {
        int count = 0, maxCount = 0;
        for (int i = 0; i < k; i++) {
            if (isVowel(s.charAt(i))) count++;
        }
        maxCount = count;
        for (int i = k; i < s.length(); i++) {
            if (isVowel(s.charAt(i - k))) count--;
            if (isVowel(s.charAt(i))) count++;
            maxCount = Math.max(maxCount, count);
        }
        return maxCount;
    }

    private boolean isVowel(char c) {
        return "aeiou".indexOf(c) != -1;
    }
}
      

var maxVowels = function(s, k) {
    const vowels = new Set(['a','e','i','o','u']);
    let count = 0, maxCount = 0;
    for (let i = 0; i < k; i++) {
        if (vowels.has(s[i])) count++;
    }
    maxCount = count;
    for (let i = k; i < s.length; i++) {
        if (vowels.has(s[i - k])) count--;
        if (vowels.has(s[i])) count++;
        maxCount = Math.max(maxCount, count);
    }
    return maxCount;
};