Variable Size: Maintain Invariant

My bias in Max Consecutive Ones III

I simulated the operation instead of maintaining an invariant.

The problem is simple: you can flip up to k zeros and need to find the maximum range you can make all 1s.

Mistake: I was tracking the length in ans even though I was already using two pointers.

Template

Iterate r, maintain a valid [l, r] window, and update the answer after the window is valid.

for r = 0; r < n; r++:
    add elem(right) to window
 
    while window is invalid:
        remove elem(left)
        left++
 
    update answer

Debug tip: always inspect the current [l, r] window.

Problems Using This Pattern

Max Consecutive Ones III

Problem: find the longest subarray that can become all 1s after flipping at most k zeros.

Invariant: zeroes <= k

Similar problems:

• Maximize the Confusion of an Exam: longest same-answer run after changing at most k answers.
• Longest Subarray of 1s After Deleting One Element: longest all-1s subarray after deleting one element.

Longest Repeating Character Replacement

Problem: find the longest substring that can become one repeated character after replacing at most k chars.

Invariant: window_len - max_freq <= k

Shrink while:

window_len - max_freq > k

Longest Substring with At Most K Distinct Characters

Problem: find the longest substring containing at most k distinct characters.

Invariant: distinct_elems <= k

Similar problem: Fruit Into Baskets is the same problem with k = 2.

Longest Substring Without Repeating Characters

Problem: find the longest substring where every character appears at most once.

Invariant: no duplicate elements.

Get Equal Substrings Within Budget

Problem: find the longest substring you can convert from s to t within maxCost.

Convert the two strings into a cost array:

cost[i] = abs(s[i] - t[i])

Then find the longest subarray whose total cost is within budget.

Invariant: window_cost <= maxCost

Minimum Operations to Reduce X to Zero

Problem: remove numbers from the ends so their sum is exactly x.

Invert the problem: find the longest positive-number subarray with sum total - x.

If the array had negative values, use prefix sum plus hashmap instead.

Frequency of the Most Frequent Element

Problem: maximize the frequency of one value using at most k increments.

Sort first. Then maintain a window where the cost to make every element equal to nums[r] is at most k.

Invariant:

cost_to_make_window_equal_to_nums_r <= k

Take K of Each Character From Left and Right

Problem: take chars from the left and right until you have at least k of each a, b, and c.

Invert the problem: taking from both ends means keeping a middle subarray.

count_in_window[ch] <= total_count[ch] - k

Number of Substrings Containing All Three Characters

Problem: count substrings that contain at least one a, b, and c.

Counting variation: once [l, r] contains a, b, and c, every extension to the right is also valid.

for r = 0; r < n; r++:
    add s[r]
 
    while window contains a, b, and c:
        ans += n - r
        remove s[l]
        l++