medium Maximum Number of Vowels in a Substring of Given Length

Problem Statement

Given a string s and an integer k, return the highest number of vowels in any substring of s that is exactly k characters long. Vowels in English are 'a', 'e', 'i', 'o', and 'u'.

Examples

Example 1:

Input: s = "azerdii", k = 4
Expected Output: 2
Justification: The substring "rdii" has two vowels ('i', 'i').

Example 2:

Input: s = "abcde", k = 2
Expected Output: 1
Justification: The substring "ab" contains one vowel ('a').

Example 3:

Input: s = "zaeixoyuxyz", k = 7
Expected Output: 5
Justification: The substring "aeixoyu" contains three vowels ('a', 'e', 'i', 'o', 'u').

Constraints:

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

Try it yourself

Try solving this question here:

✅ Solution Maximum Number of Vowels in a Substring of Given Length

Problem Statement

Given a string s and an integer k, return the highest number of vowels in any substring of s that is exactly k characters long. Vowels in English are 'a', 'e', 'i', 'o', and 'u'.

Examples

Example 1:

Input: s = "azerdii", k = 4
Expected Output: 2
Justification: The substring "rdii" has two vowels ('i', 'i').

Example 2:

Input: s = "abcde", k = 2
Expected Output: 1
Justification: The substring "ab" contains one vowel ('a').

Example 3:

Input: s = "zaeixoyuxyz", k = 7
Expected Output: 5
Justification: The substring "aeixoyu" contains three vowels ('a', 'e', 'i', 'o', 'u').

Constraints:

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

Solution

To solve this problem, we will use a sliding window approach. This method allows us to efficiently keep track of the number of vowels in any substring of length k as we move through the string. We start by counting the vowels in the first k characters. Then, we slide the window one character to the right at a time, adjusting the vowel count by subtracting the character that is left behind and adding the new character that enters the window.

This approach is effective because it avoids recalculating the number of vowels from scratch for every substring, which would be inefficient. Instead, it updates the count in constant time, making the overall time complexity linear in relation to the length of the string.

Step-by-step Algorithm

Initialization:
- Initialize two variables: maxVowels to keep track of the maximum number of vowels found in any window, and currentVowels to count the number of vowels in the current window.
- Define a helper function isVowel(char ch) to check if a character is a vowel.
First Window Setup:
- Iterate over the first k characters of the string s.
- For each character in this range, check if it is a vowel using isVowel(). If it is, increment currentVowels.
Store Initial Count:
- Set maxVowels to the value of currentVowels after processing the first k characters.
Sliding Window:
- Iterate from the kth character to the end of the string.
- For each character at position i:
  - Check if the character at position i is a vowel. If it is, increment currentVowels.
  - Check if the character at position i - k is a vowel. If it is, decrement currentVowels.
  - Update maxVowels to be the maximum of maxVowels and currentVowels.
Return Result:
- Return the value of maxVowels.

Algorithm Walkthrough

Let's consider the input: s = "zaeixoyuxyz", k = 7

Initialization:
- maxVowels = 0
- currentVowels = 0
- Define isVowel(char ch) to check if a character is 'a', 'e', 'i', 'o', or 'u'.
First Window Setup (characters: 'z', 'a', 'e', 'i', 'x', 'o', 'y'):
- i = 0, s[0] = 'z' → Not a vowel, currentVowels = 0
- i = 1, s[1] = 'a' → Vowel, currentVowels = 1
- i = 2, s[2] = 'e' → Vowel, currentVowels = 2
- i = 3, s[3] = 'i' → Vowel, currentVowels = 3
- i = 4, s[4] = 'x' → Not a vowel, currentVowels = 3
- i = 5, s[5] = 'o' → Vowel, currentVowels = 4
- i = 6, s[6] = 'y' → Not a vowel, currentVowels = 4
Store Initial Count:
- maxVowels = 4
Sliding Window:
- i = 7, s[7] = 'u' → Vowel, currentVowels = 5
  - s[7-7] = s[0] = 'z' → Not a vowel, currentVowels = 5
  - maxVowels = max(4, 5) = 5
- i = 8, s[8] = 'x' → Not a vowel, currentVowels = 5
  - s[8-7] = s[1] = 'a' → Vowel, currentVowels = 4
  - maxVowels = max(5, 4) = 5
- i = 9, s[9] = 'y' → Not a vowel, currentVowels = 4
  - s[9-7] = s[2] = 'e' → Vowel, currentVowels = 3
  - maxVowels = max(5, 3) = 5
- i = 10, s[10] = 'z' → Not a vowel, currentVowels = 3
  - s[10-7] = s[3] = 'i' → Vowel, currentVowels = 2
  - maxVowels = max(5, 2) = 5
Return Result:
- Return maxVowels = 5

Code

java

class Solution {

  public int maxVowels(String s, int k) {
    int maxVowels = 0;
    int currentVowels = 0;

    // Initialize the first window
    for (int i = 0; i < k; i++) {
      if (isVowel(s.charAt(i))) {
        currentVowels++;
      }
    }

    maxVowels = currentVowels;

    // Slide the window across the string
    for (int i = k; i < s.length(); i++) {
      if (isVowel(s.charAt(i))) {
        currentVowels++;
      }
      if (isVowel(s.charAt(i - k))) {
        currentVowels--;
      }
      maxVowels = Math.max(maxVowels, currentVowels);
    }

    return maxVowels;
  }

  private boolean isVowel(char ch) {
    return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(solution.maxVowels("azerdii", 4)); // Output: 2
    System.out.println(solution.maxVowels("abcde", 2)); // Output: 1
    System.out.println(solution.maxVowels("zaeixoyuxyz", 7)); // Output: 5
  }
}

Complexity Analysis

Time Complexity: , where n is the length of the string. This is because we scan the string once to initialize the first window and then slide the window across the string.
Space Complexity: . We use a constant amount of extra space regardless of the size of the input.

🤖 Don't fully get this? Learn it with Claude

Stuck on Maximum Number of Vowels in a Substring of Given Length? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Maximum Number of Vowels in a Substring of Given Length** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Maximum Number of Vowels in a Substring of Given Length** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Maximum Number of Vowels in a Substring of Given Length**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Maximum Number of Vowels in a Substring of Given Length**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Maximum Average Subarray I Max Consecutive Ones III →