Leet Code - Sliding Window - Maximum Number of Vowels in a Substring of Given Length

🧩 Problem: Maximum Number of Vowels in a Substring of Given Length

---

📝 Problem Description:

Given a string s and an integer k, find the maximum number of vowels in any substring of s with length k.

Vowels = {a, e, i, o, u} (case-sensitive: assume lowercase)

---

1️⃣ Brute-force Approach (Naive)

---

🔍 Idea:

• Check every substring of length k

• Count vowels in each substring

• Keep track of the max count

---

🧑‍💻 Code:

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

int maxVowels(string s, int k) {
    int maxCount = 0;
    int n = s.size();
    
    for (int i = 0; i <= n - k; i++) {
        int count = 0;
        for (int j = i; j < i + k; j++) {
            if (isVowel(s[j])) {
                count++;
            }
        }
        maxCount = max(maxCount, count);
    }
    
    return maxCount;
}

---

⏳ Time Complexity:

• Outer loop: runs n-k+1 times → ~O(n)

• Inner loop: runs k times for each outer loop iteration

• Total: O(n * k)

💾 Space Complexity:

• Just some counters and booleans → O(1)

---

🔍 Step-by-step for s = "abciiidef", k = 3

i	Substring	Vowels in substring	maxCount updates to
0	"abc"	a = 1	1
1	"bci"	i = 1	1
2	"cii"	i, i = 2	2
3	"iii"	i, i, i = 3	3
4	"iid"	i, i = 2	3
5	"ide"	i, e = 2	3
6	"def"	e = 1	3

---

2️⃣ Sliding Window Approach (Optimal)

---

🔍 Idea:

• Use a window of size k

• Slide it from left to right

• Add new char at right, remove old char at left from count if vowel

• Track max count along the way

---

🧑‍💻 Code:

int maxVowels(string s, int k) {
    int maxCount = 0, count = 0;
    int n = s.size();
    
    for (int i = 0; i < k; i++) {
        if (isVowel(s[i])) count++;
    }
    maxCount = count;

    for (int i = k; i < n; i++) {
        if (isVowel(s[i])) count++;            // Add right char
        if (isVowel(s[i - k])) count--;        // Remove left char
        maxCount = max(maxCount, count);
    }
    
    return maxCount;
}

---

⏳ Time Complexity:

• We do one pass → O(n)

💾 Space Complexity:

• Only counters → O(1)

---

🔍 Step-by-step for s = "abciiidef", k = 3

Iteration (i)	Window	Count Change	count	maxCount
Initial (0-2)	"abc"	a is vowel → count = 1	1	1
3	"bci" → "cii"	Remove b(not vowel), add i(vowel) → count=2	2	2
4	"cii" → "iii"	Remove c(not vowel), add i(vowel) → count=3	3	3
5	"iii" → "iid"	Remove i(vowel), add d(not vowel) → count=2	2	3
6	"iid" → "ide"	Remove i(vowel), add e(vowel) → count=2	2	3
7	"ide" → "def"	Remove i(vowel), add f(not vowel) → count=1	1	3

---

🔥 Summary:

Approach	Time Complexity	Space Complexity	Explanation
Brute Force	O(n * k)	O(1)	Count vowels every window
Sliding Window	O(n)	O(1)	Update counts by adding/removing 1

---