# Maximum Number of Vowels in a Substring of Given Length
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-vowels-in-a-substring-of-given-length
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** String
**Companies:** [Turing](https://scaleengineer.com/companies/turing), [Wayfair](https://scaleengineer.com/companies/wayfair)
---
## Problem
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 <= 105`
* `s` consists of lowercase English letters.
* `1 <= k <= s.length`

# Approaches
## Brute Force: Checking Every Substring
The most straightforward approach is to generate every possible substring of length `k`, count the number of vowels in each one, and keep track of the maximum count found.
**Time:** O(N * K), where N is the length of the string `s`. We iterate through `N - K + 1` possible starting positions for the substring. For each substring, we iterate `K` times to count the vowels. This results in a nested loop structure, leading to a time complexity that can be approximated as O(N * K). · **Space:** O(1). We only use a few variables to store the maximum count and the current count, which does not depend on the input size.
**Pros:** Simple to understand and implement.
**Cons:** Inefficient for large inputs, as it re-calculates the vowel count for overlapping parts of substrings repeatedly.; Will likely result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
### Explanation
This method involves a nested loop. The outer loop iterates through all possible starting positions of a substring of length `k`. The inner loop then iterates through each character of that substring to count the vowels.
```java
class Solution {
    public int maxVowels(String s, int k) {
        int maxVowels = 0;
        // Outer loop for all possible start indices of a substring of length k
        for (int i = 0; i <= s.length() - k; i++) {
            int currentVowels = 0;
            // Inner loop to count vowels in the current substring
            for (int j = i; j < i + k; j++) {
                if (isVowel(s.charAt(j))) {
                    currentVowels++;
                }
            }
            maxVowels = Math.max(maxVowels, currentVowels);
        }
        return maxVowels;
    }

    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}
```
While simple, this approach is inefficient because it repeatedly scans overlapping portions of the string.
### Algorithm
- Initialize a variable `max_vowels` to 0.
- Iterate through the string `s` from index `i` = 0 to `s.length() - k`.
- For each `i`, consider the substring of length `k` starting at `i`.
- Initialize a `current_vowels` count to 0 for this substring.
- Iterate from `j` = `i` to `i + k - 1`.
- If the character at `s.charAt(j)` is a vowel, increment `current_vowels`.
- After counting vowels for the current substring, update `max_vowels = max(max_vowels, current_vowels)`.
- After the outer loop finishes, return `max_vowels`.

## Sliding Window
A more efficient approach is to use the sliding window technique. We maintain a 'window' of size `k` and slide it across the string one character at a time. Instead of recounting all vowels in the new window, we update the count by considering only the character that enters the window and the character that leaves it. This avoids redundant work.
**Time:** O(N), where N is the length of the string `s`. We perform an initial scan of `K` elements, followed by a single pass through the remaining `N - K` elements. Each step in the sliding window takes constant time. Thus, the total time complexity is O(K + (N - K)) = O(N). · **Space:** O(1). We only use a constant amount of extra space for variables to store the current and maximum vowel counts.
**Pros:** Highly efficient with linear time complexity.; Optimal solution for this problem as it avoids redundant calculations.
**Cons:** Slightly more complex to conceptualize than the brute-force approach.
### Explanation
We start by calculating the vowel count for the initial window of the first `k` characters. This count becomes our initial maximum. Then, we iterate from the `k`-th character to the end of the string. In each step, we slide the window one position to the right. This is done by:
1.  Checking if the character leaving the window (at the far left) is a vowel. If so, we decrement our current vowel count.
2.  Checking if the character entering the window (at the far right) is a vowel. If so, we increment our current vowel count.
After each slide, we update our overall maximum vowel count. This process ensures we only perform a single pass through the string.
```java
class Solution {
    public int maxVowels(String s, int k) {
        int currentVowels = 0;
        // 1. Calculate vowels in the first window of size k
        for (int i = 0; i < k; i++) {
            if (isVowel(s.charAt(i))) {
                currentVowels++;
            }
        }
        int maxVowels = currentVowels;

        // 2. Slide the window across the rest of the string
        for (int i = k; i < s.length(); i++) {
            // Subtract the vowel count of the character that is leaving the window
            if (isVowel(s.charAt(i - k))) {
                currentVowels--;
            }
            // Add the vowel count of the character that is entering the window
            if (isVowel(s.charAt(i))) {
                currentVowels++;
            }
            // Update the maximum
            maxVowels = Math.max(maxVowels, currentVowels);
        }
        return maxVowels;
    }

    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}
```
### Algorithm
- Define a helper function `isVowel(char c)` to check for vowels in O(1) time.
- Initialize a `current_vowels` count by iterating through the first `k` characters of the string `s`.
- Initialize `max_vowels` with this initial `current_vowels` count.
- Iterate through the string from index `i` = `k` to `s.length() - 1`. This loop represents the sliding of the window.
- In each iteration, the window slides one position to the right:
    - The character `s.charAt(i - k)` leaves the window. If it's a vowel, decrement `current_vowels`.
    - The character `s.charAt(i)` enters the window. If it's a vowel, increment `current_vowels`.
- Update `max_vowels = max(max_vowels, current_vowels)` after each slide.
- Return `max_vowels`.

# Solutions
### Java

```java
class Solution {
public
  int maxVowels(String s, int k) {
    int t = 0, n = s.length();
    for (int i = 0; i < k; ++i) {
      if (isVowel(s.charAt(i))) {
        ++t;
      }
    }
    int ans = t;
    for (int i = k; i < n; ++i) {
      if (isVowel(s.charAt(i))) {
        ++t;
      }
      if (isVowel(s.charAt(i - k))) {
        --t;
      }
      ans = Math.max(ans, t);
    }
    return ans;
  }
private
  boolean isVowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxVowels(string s, int k) {
    int t = 0, n = s.size();
    for (int i = 0; i < k; ++i)
      t += isVowel(s[i]);
    int ans = t;
    for (int i = k; i < n; ++i) {
      t += isVowel(s[i]);
      t -= isVowel(s[i - k]);
      ans = max(ans, t);
    }
    return ans;
  }
  bool isVowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
  }
};

```

### Python

```python
class Solution:
    def maxVowels(self, s: str, k: int) -> int: vowels = set('aeiou') t = sum(c in vowels for c in s[: k]) ans = t for i in range(k, len(s)): t += s[i] in vowels t -= s[i - k] in vowels ans = max(ans, t) return ans

```