1. Problem Overview

This problem tests your understanding of string manipulation and the sliding window technique.

The goal is to find the maximum number of vowels that appear in any substring of length k within a given string s.

---

Problem Statement (LeetCode 1456)

Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k.

---

Example 1:

Input: s = "abciiidef", k = 3
Output: 3
Explanation:
The substring "iii" has 3 vowels.

Example 2:

Input: s = "aeiou", k = 2
Output: 2
Explanation:
Every substring of length 2 has 2 vowels.

Example 3:

Input: s = "leetcode", k = 3
Output: 2
Explanation:
The substring "lee" has 2 vowels.

---

2. Understanding the Problem

We are asked to find the maximum count of vowels (a, e, i, o, u) present in any substring of length k.

Key Observations

• You do not need to extract substrings explicitly.
• Instead, you can slide a window of size k across the string and track how many vowels are inside.
• Each time the window slides by one position:
  • Remove the effect of the character that moves out.
  • Add the effect of the character that comes in.

This way, we maintain the vowel count efficiently in O(n) time.

---

3. Example Walkthrough

Let’s take:

s = "abciiidef", k = 3

Step-by-step window movement:

Window	Vowels in Window	Count
“abc”	a	1
“bci”	i	1
“cii”	i, i	2
“iii”	i, i, i	3
“iid”	i, i	2
“ide”	i, e	2
“def”	e	1

Maximum = 3 (from window “iii”)

---

4. Step-by-Step Approach (Sliding Window)

1. Define a helper method isVowel(char c) to check if a character is a vowel.
2. Initialize two variables:
   • count = current number of vowels in the current window.
   • maxCount = maximum number of vowels seen so far.
3. Traverse the string:
   • For each new character that enters the window:
     • Increment count if it’s a vowel.
   • If window size exceeds k:
     • Remove the character that moves out of the window and decrement count if it’s a vowel.
   • Update maxCount with the current count.
4. Return maxCount.

---

5. Java Implementation

public class MaxVowelsInSubstring {

    public int maxVowels(String s, int k) {
        int maxCount = 0;
        int currentCount = 0;
        
        // Helper lambda to check vowel
        java.util.function.Predicate<Character> isVowel = 
            c -> "aeiou".indexOf(c) != -1;

        for (int i = 0; i < s.length(); i++) {
            // Add new character
            if (isVowel.test(s.charAt(i))) {
                currentCount++;
            }

            // Remove the character that slides out of window
            if (i >= k && isVowel.test(s.charAt(i - k))) {
                currentCount--;
            }

            // Update maximum vowels found
            maxCount = Math.max(maxCount, currentCount);
        }

        return maxCount;
    }

    public static void main(String[] args) {
        MaxVowelsInSubstring obj = new MaxVowelsInSubstring();

        System.out.println("Example 1: " + obj.maxVowels("abciiidef", 3)); // 3
        System.out.println("Example 2: " + obj.maxVowels("aeiou", 2));     // 2
        System.out.println("Example 3: " + obj.maxVowels("leetcode", 3));  // 2
    }
}

---

6. Dry Run Example

Let’s dry-run the algorithm for s = "abciiidef", k = 3.

i	char	currentCount	maxCount	Window
0	a	1	1	a
1	b	1	1	ab
2	c	1	1	abc
3	i	2	2	bci
4	i	3	3	cii
5	i	3	3	iii
6	d	2	3	iid
7	e	2	3	ide
8	f	1	3	def

Final maxCount = 3

---

7. Complexity Analysis

Type	Complexity	Explanation
Time Complexity	O(n)	Each character is processed at most twice (enter and exit the window).
Space Complexity	O(1)	Only constant extra variables used.

---

8. Edge Cases

1. All vowels
   Input: s = "aeiou", k = 5 → Output: 5
   (Whole string is vowels)
2. No vowels
   Input: s = "bcdfg", k = 3 → Output: 0
3. String shorter than k
   Input: s = "abc", k = 5 → Output: 1
   (Process till end without sliding)
4. Large k value
   Input: large strings with k close to n; still O(n) performance due to window method.

---

9. Alternate Implementation (Without Lambda)

If you prefer not using a lambda function, a simpler isVowel method works too:

public class MaxVowelsInSubstring {

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

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

        for (int i = 0; i < s.length(); i++) {
            if (isVowel(s.charAt(i))) {
                count++;
            }
            if (i >= k && isVowel(s.charAt(i - k))) {
                count--;
            }
            maxCount = Math.max(maxCount, count);
        }

        return maxCount;
    }

    public static void main(String[] args) {
        MaxVowelsInSubstring obj = new MaxVowelsInSubstring();
        System.out.println(obj.maxVowels("abciiidef", 3)); // 3
        System.out.println(obj.maxVowels("aeiou", 2));     // 2
        System.out.println(obj.maxVowels("leetcode", 3));  // 2
    }
}

---

10. Key Takeaways

• Sliding window is a crucial technique for problems involving fixed-size substrings.
• Maintaining a running count of vowels allows O(1) updates per character.
• Always handle window exit and entry updates carefully to avoid off-by-one errors.
• This problem helps build a foundation for more advanced window-based problems like:
  • Longest substring with k distinct characters.
  • Maximum average subarray.
  • Substring replacement or transformation.