Maximum Number of Vowels in a Substring of Given Length

Master this topic with zero to advance depth.

Maximum Number of Vowels in a Substring of Given Length

Find the maximum number of vowels in any substring of length k.

Visual Representation

s = "abciiidef", k = 3

Window [abc] -> Vowels: 1 (a)
Window [bci] -> Vowels: 1 (i)
Window [cii] -> Vowels: 2 (i, i)
Window [iii] -> Vowels: 3 (i, i, i) -> MAX

Medium

Examples

Input: s = "abciiidef", k = 3
Output: 3

Approach 1

Level I: Brute Force

Intuition

Iterate through all possible strings of length k. For each substring, count the number of vowels manually by iterating through characters.

Thought Process

Iterate i from 0 to n - k.
Extract substring s[i : i+k].
Count vowels in the substring.
Track the maximum count observed.

⏱ O(N * K)💾 O(1) (excluding substring storage if any)

Detailed Dry Run

Substring	Vowels	Max
abc	a (1)	1
bci	i (1)	1
cii	i, i (2)	2
iii	i, i, i (3)	3

java

public class Main {
    public static int maxVowels(String s, int k) {
        int maxV = 0;
        String vowels = "aeiou";
        for (int i = 0; i <= s.length() - k; i++) {
            int currentV = 0;
            for (int j = i; j < i + k; j++) {
                if (vowels.indexOf(s.charAt(j)) != -1) currentV++;
            }
            maxV = Math.max(maxV, currentV);
        }
        return maxV;
    }

    public static void main(String[] args) {
        System.out.println(maxVowels("abciiidef", 3)); // 3
    }
}

Approach 2

Level II: Prefix Sums for Vowels (O(N) Space)

Intuition

We can precompute an array vowelCount where vowelCount[i] stores the number of vowels from index 0 to i-1. The number of vowels in any substring s[i...i+k-1] can be calculated as vowelCount[i+k] - vowelCount[i].

Thought Process

Initialize an array prefix of size n + 1.
Iterate through the string; if s[i] is a vowel, prefix[i+1] = prefix[i] + 1, otherwise prefix[i+1] = prefix[i].
Iterate i from 0 to n - k and track max(prefix[i+k] - prefix[i]).

Pattern: Multi-pass Optimization

⏱ O(N) - One pass to build prefix array, one to find max.💾 O(N) - To store the prefix sum array.

java

public class Main {
    public static int maxVowels(String s, int k) {
        int n = s.length();
        int[] prefix = new int[n + 1];
        String vowels = "aeiou";
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + (vowels.indexOf(s.charAt(i)) != -1 ? 1 : 0);
        }
        int maxV = 0;
        for (int i = 0; i <= n - k; i++) {
            maxV = Math.max(maxV, prefix[i + k] - prefix[i]);
        }
        return maxV;
    }
}

Approach 3

Level III: Optimal (Fixed Sliding Window)

Intuition

Thought Process

This is a classic fixed-size sliding window problem. We maintain a count of vowels. When a new character enters the window, we increment if it's a vowel. When a character leaves, we decrement if it was a vowel.

Patterns

Fixed size k: Window is always exactly k wide.
O(1) Update: Only the entering and leaving characters change the state.

⏱ O(N)💾 O(1)

Detailed Dry Run

Window	Vowel Count	Max Count
[abc]	1	1
[bci]	1	1
[cii]	2	2
[iii]	3	3

java

public class Main {
    public static int maxVowels(String s, int k) {
        int maxV = 0, curV = 0;
        String vowels = "aeiou";
        for (int i = 0; i < s.length(); i++) {
            if (vowels.indexOf(s.charAt(i)) != -1) curV++;
            if (i >= k) {
                if (vowels.indexOf(s.charAt(i - k)) != -1) curV--;
            }
            maxV = Math.max(maxV, curV);
        }
        return maxV;
    }

    public static void main(String[] args) {
        System.out.println(maxVowels("abciiidef", 3));
    }
}

⚠️ Common Pitfalls & Tips

Be careful with string indexing. The check for leaving elements should happen once the index i is >= k.

← Previous QuestionGrumpy Bookstore Owner

Next Question →Subarray Product Less Than K

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.