1456. Maximum Number of Vowels in a Substring of Given Length

Difficulty: MEDIUM

Problem description can be found here.

Approach

What is This Problem?

Given a binary array nums and an integer k, you may flip at most k zeros to ones. Return the length of the longest consecutive subarray that contains only 1s after performing at most k flips.

Why This Works (Dynamic Sliding Window)

The problem is equivalent to: Find the longest subarray that contains at most k zeros. Within such a window, we can flip those zeros (if any) to ones, resulting in a subarray of all ones. The window length itself is the answer because after flipping at most k zeros, all elements become 1. So maximizing window length under the constraint yields the solution.

A dynamic sliding window efficiently scans all possible subarrays in O(n) time:

• Expand the window to the right, counting zeros.
• When zeros exceed k, shrink from the left until zeros ≤ k again.
• At each valid window, update the maximum length.

Algorithm Steps

1. Initialize left = 0, zeroCount = 0, maxLen = 0.
2. Iterate right from 0 to n-1:
   • If nums[right] === 0, increment zeroCount.
   • While zeroCount > k:
     • If nums[left] === 0, decrement zeroCount.
     • Increment left.
   • Now window [left, right] has at most k zeros and is valid.
   • Update maxLen = max(maxLen, right - left + 1).
3. Return maxLen.

Visualization

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

We want longest subarray with ≤2 zeros.

Step-by-step:

R0 (1): zeros=0 → window [0..0] size=1 → max=1
R1 (0): zeros=1 → window [0..1] size=2 → max=2
R2 (1): zeros=1 → window [0..2] size=3 → max=3
R3 (0): zeros=2 → window [0..3] size=4 → max=4
R4 (1): zeros=2 → window [0..4] size=5 → max=5
R5 (1): zeros=2 → window [0..5] size=6 → max=6 ✓
R6 (0): zeros=3 → shrink until zeros≤2:
   left=0 (1) → left=1
   left=1 (0) → zeros=2, left=2
   Now window [2..6] size=5, max stays 6

Largest window: length 6, subarray [1,0,1,0,1,1] (2 zeros), flip them → all ones.

Key Pattern

• Variable-size sliding window with a constraint on a count (zeros ≤ k).
• Two pointers (left, right) and a counter.
• Expand right pointer each iteration, shrink left while constraint violated.
• Each element enters and exits window at most once → O(n) time, O(1) space.

When to Use This Pattern

• Problems asking “longest subarray with at most K [something]” (zeros, distinct chars, replacements, etc.)
• Flipping/replacing up to K elements to maximize something.
• Generalizable: maintain a condition that can be updated incrementally as window slides.

Solution

function longestOnes(nums: number[], k: number): number {
  let result = 0;
  let left = 0;
  let zeroCount = 0;

  for (let right = 0; right < nums.length; right++) {
    if (nums[right] === 0) {
      zeroCount += 1;
    }

    while (zeroCount > k) {
      if (nums[left] === 0) zeroCount -= 1;
      left += 1;
    }

    result = Math.max(result, right - left + 1);
  }

  return result;
}

longestOnes([1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], 2); // 6 [1,1,1,0,0,1*,1,1,1,1,1*]

Resources

https://www.youtube.com/watch?v=HsGKI02yw6M