When validity is a computed quantity

Sometimes the window is legal or not based on a number you have to derive rather than read.

A window with a budget

In the last lesson, legality was something you could read directly: a total, a count of distinct characters. Now consider a window that is allowed a limited number of changes.

The concrete version: given a list of 0s and 1s, and a budget of k flips from 0 to 1, what is the longest stretch you can make all 1s?

Why it works

What does the budget buy?

The window is legal when the number of 0s inside it is at most k, because each 0 costs one flip. So the state to carry is a count of zeros, and the rule is a comparison against k.

That is the whole derivation, and it is worth doing explicitly on paper for any problem of this shape. The mechanics are already known; the question is always what quantity the budget is being spent on.

1def longest_all_ones_after_flips(bits, k):2    left = 03    zeros = 04    best = 05 6    for right in range(len(bits)):7        if bits[right] == 0:8            zeros += 19 10        while zeros > k:11            if bits[left] == 0:12                zeros -= 113            left += 114 15        best = max(best, right - left + 1)16 17    return best18 19print(longest_all_ones_after_flips([1, 1, 0, 0, 1, 1, 1, 0, 1], 2))

Quick check· 5 min

How many replacements does this window need?

A window holds the characters AABABBA and you may replace characters to make them all identical. How many replacements does it need, and how is that computed?

3, from window size 7 minus 4 occurrences of the most common character A4, because there are 4 As and every other character must change to match them2, the count of the least common character B minus one6, since every character except one must be replaced

Find the bug· 5 min

Find the window bug

This is meant to find the longest stretch with at most k zeros. It reports windows that are too long. Click the line that is wrong.

Click the line you think is wrong

Complexity· 5 min

Cost of the flip window

Time and space for longest_all_ones_after_flips on a list of n bits.

Problem· 25 min

Longest Repeating Character Replacement

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

CodeGround