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 five vowels ('a', 'e', 'i', 'o', 'u').

Constraints:

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

Pattern

Fixed-size sliding window with an indicator aggregate. Same shape as maximum-average: window width locked to k. The tracked state is not a sum of values but a count of vowels — still reversible: when a vowel enters, +1; when a vowel leaves, -1; non-vowels change nothing. Recognition signal: "exactly k characters" + "count how many satisfy property P".

When-not: "longest substring with at most k vowels" is a variable window (shrink while count exceeds k). "Count total vowels in the whole string" needs no window at all.

Complexity: O(k) to seed the first window + O(n−k) slides with O(1) vowel checks each → O(n) time, O(1) space (vowel set is five letters).

Solution

Use a fixed-size sliding window of length k. Count vowels in the first k characters, then slide one character at a time: if the new character is a vowel, increment; if the character leaving the window is a vowel, decrement. Track the maximum count seen.

Each slide updates the count in O(1) instead of rescanning the whole window, so total time is linear in the length of the string.

Step-by-step Algorithm

1. 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.

2. 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.

3. Store Initial Count:

   • Set maxVowels to the value of currentVowels after processing the first k characters.

4. 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.

5. Return Result:

   • Return the value of maxVowels.

Algorithm Walkthrough

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

1. Initialization:

   • maxVowels = 0
   • currentVowels = 0
   • Define isVowel(char ch) to check if a character is 'a', 'e', 'i', 'o', or 'u'.

2. 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

3. Store Initial Count:

   • maxVowels = 4

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

5. Return Result:

   • Return maxVowels = 5

Code

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.

🎯 STRICT STANDOUT — Max Vowels in Substring of Length k

1. Why / judgment

Fixed window with a reversible indicator: +1 when a vowel enters, −1 when a vowel leaves. You never rescan k chars. Recognition signal: “exactly k” + “count property P”.

2. Walkthrough recompute + complexity (K11)

s="zaeixoyuxyz", k=7
First window "zaeixoy": vowels a,e,i,o → 4
i=7 'u' in, 'z' out → 5; max=5  ("aeixoyu")
i=8 'x' in, 'a' out → 4
i=9 'y' in, 'e' out → 3
i=10 'z' in, 'i' out → 2
answer 5 ✓

Vowel check O(1); seed O(k); slides O(n−k) → Θ(n) time, Θ(1) space
Rescan each window: Θ(n·k) — fails spirit of n=1e5 when k large.

3. Pattern — FIXED WINDOW + INDICATOR AGGREGATE (K12)

Name: Count-P in every k-window.

Recognition: exactly k length; maximize count of a boolean property.

When-NOT: “longest with ≤k vowels” → variable window; whole-string vowel count → single pass no window; anagrams of pattern → need frequency map + match count, still often fixed window of pattern length.

4. Edge hand-run (K13)

s="abcde", k=2 → windows ab,bc,cd,de → vowels 1,0,0,1 → max 1
s="aeiou", k=5 → 5
s="xyz", k=1 → 0 (no vowels)
Only consonants → 0

5. Interviewer follow-ups

Q1. Why O(n) not O(nk)?
A: Incremental ±1 on boundary chars only.

Q2. Is 'y' a vowel here?
A: No — only a,e,i,o,u per problem.

Q3. Variable “at most k vowels” approach?
A: Expand R; while vowels>k shrink L; track max length — different template.

Problem Statement

Given a binary array nums containing only 0 and 1 and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.

Examples

Example 1:

• Input: nums = [1, 0, 0, 1, 1, 0, 1, 1], k = 2
• Expected Output: 6
• Justification: By flipping 0 at the second and fifth index in the list, we get [1, 0, 1, 1, 1, 1, 1, 1], which has 6 consecutive 1s.

Example 2:

• Input: nums = [1, 0, 1, 1, 0, 0, 1, 1], k = 1
• Expected Output: 4
• Justification: By flipping 0 at 1st index, we get [1, 1, 1, 1, 0, 1, 1, 1], with a maximum of 4 consecutive 1s.

Example 3:

• Input: nums = [1, 0, 0, 1, 1, 0, 1], k = 3
• Expected Output: 7
• Justification: By flipping all three zeros, we get [1, 1, 1, 1, 1, 1, 1], which has 7 consecutive 1s.

Constraints:

• 1 <= nums.length <= 10⁵
• nums[i] is either 0 or 1.
• 0 <= k <= nums.length

Pattern

Variable-size sliding window — "longest valid window with budget k." Recognition: maximize length of a contiguous segment subject to a numeric budget (here, at most k zeros / flips). Template: expand right always; while the window is invalid (zero_count > k), shrink left until valid; record right - left + 1 after each fix-up. Each index enters and leaves at most once → O(n).

Family links: Longest Subarray of 1's After Deleting One Element is the same template with k = 1 and answer length reduced by 1 (must delete). "Longest substring with at most K distinct characters" uses the same expand/shrink skeleton with a frequency map instead of a zero counter.

When-not / edges: k = 0 reduces to longest run of pure 1s; k ≥ number of zeros → whole array. The shrink loop must be a while, not an if — one expand can introduce a zero that requires multiple left moves if several zeros cluster.

Solution

Keep a window that may contain at most k zeros (each zero is one flip spent). Expand the right end; when zero_count > k, advance the left end until the window is valid again. The longest valid window length is the answer — that many consecutive 1s after at most k flips.

Each pointer moves at most n times, so the run is linear. The invariant "zeros in [left, right] ≤ k" guarantees every recorded length is achievable with ≤ k flips.

Step-by-step Algorithm

1. Initialization:

   • Initialize two pointers left and right to 0.
   • Initialize max_length to 0 to keep track of the maximum length of consecutive 1s found.
   • Initialize zero_count to 0 to keep track of the number of 0s in the current window.

2. Expand the window:

   • While right is less than the length of the list nums:
     • If the element at nums[right] is 0, increment zero_count by 1.
     • While zero_count exceeds k (i.e., more than k 0s in the current window):
       • If the element at nums[left] is 0, decrement zero_count by 1.
       • Move the left pointer to the right by 1.
     • Update max_length to be the maximum of its current value and the length of the current window (right - left + 1).
     • Move the right pointer to the right by 1.

3. Return the result:

   • After the loop ends, return max_length as the result.

Algorithm Walkthrough

Input: nums = [1, 0, 0, 1, 1, 0, 1, 1], k = 2

1. Initialization:

   • left = 0
   • right = 0
   • max_length = 0
   • zero_count = 0

2. First Iteration (right = 0):

   • nums[0] is 1.
   • zero_count remains 0.
   • max_length is updated to 1 (window: [1]).
   • Increment right to 1.

3. Second Iteration (right = 1):

   • nums[1] is 0.
   • Increment zero_count to 1.
   • max_length is updated to 2 (window: [1, 0]).
   • Increment right to 2.

4. Third Iteration (right = 2):

   • nums[2] is 0.
   • Increment zero_count to 2.
   • max_length is updated to 3 (window: [1, 0, 0]).
   • Increment right to 3.

5. Fourth Iteration (right = 3):

   • nums[3] is 1.
   • zero_count remains 2.
   • max_length is updated to 4 (window: [1, 0, 0, 1]).
   • Increment right to 4.

6. Fifth Iteration (right = 4):

   • nums[4] is 1.
   • zero_count remains 2.
   • max_length is updated to 5 (window: [1, 0, 0, 1, 1]).
   • Increment right to 5.

7. Sixth Iteration (right = 5):

   • nums[5] is 0.
   • Increment zero_count to 3.
   • zero_count exceeds k, so start adjusting left:
     • nums[0] is 1, zero_count remains 3, increment left to 1.
     • nums[1] is 0, decrement zero_count to 2, increment left to 2.
   • max_length remains 5 (window: [0, 1, 1, 0]).
   • Increment right to 6.

8. Seventh Iteration (right = 6):

   • nums[6] is 1.
   • zero_count remains 2.
   • max_length is updated to 5 (window: [0, 1, 1, 0, 1]).
   • Increment right to 7.

9. Eighth Iteration (right = 7):

   • nums[7] is 1.
   • zero_count remains 2.
   • max_length is updated to 6 (window: [0, 1, 1, 0, 1, 1]).
   • Increment right to 8, which ends the loop as right equals the length of nums.

10. Return Result:

    • The final value of max_length is 6.

Code

Complexity Analysis

Time Complexity:

• The algorithm uses a sliding window approach with two pointers (left and right), which traverse the array only once. Hence, the overall time complexity is , where n is the length of the array.

Space Complexity:

• The algorithm uses a constant amount of extra space (only a few integer variables), so the space complexity is .

🎯 STRICT STANDOUT: Why / worked+complexity / pattern+when-not / edge / drills — Solution Max Consecutive Ones III

Why this concept exists (judgment layer)

Longest window with budget k (≤k zeros/flips) is the variable-window skeleton shared by 'at most K distinct' and 'delete one zero' siblings. while-not-if on shrink is the bug that silently fails clustered zeros.

Worked example with complexity derivation

nums=[1,0,0,1,1,0,1,1], k=2:
Expand right; zero_count tracks flips spent.
At right=5 third zero: zero_count=3>2 → shrink left past index 0 (one) then 1 (zero) → count=2;
window [0,1,1,0] len 4; continue → final max_length=6 (window indices 2..7).
Each index enters/leaves once → time Θ(n), space Θ(1).
Invariant: zeros in [L,R] ≤ k ⇒ length achievable with ≤k flips.

Pattern + when-NOT / named alternative

PATTERN: variable window — expand R always; while invalid shrink L; record len. Family: Longest 1s after delete one = k=1 with answer len-1; at most K distinct → freq map budget. WHEN NOT: fixed k length maximize vowels → fixed window. Need exactly k flips used → same template still works for max length (extra flips free). Subsequence non-contiguous → not window.

Edge case / failure mode

Edges: k=0 → longest pure 1-run; k≥#zeros → n; all zeros k=2 → 2. Failure: if instead of while: one shrink may leave zero_count>k when multiple zeros exit needed.

Hostile-panel drills (defend the decision)

Q1. Why while zero_count>k not if?
Model answer: One right step can push count over k by 1, but left may need multiple moves to drop enough zeros.

Q2. Complexity derivation.
Model answer: L and R each 0..n-1 at most once → O(n) pointer moves.

Q3. k=0 on [1,1,0,1,1]?
Model answer: Windows cannot include zeros → longest pure 1s = 2.