Budgeted Sliding Window

Foundations

So far, a window either kept a fixed size or shrank the moment its rule broke. Now, what if the window may hold a few elements that break the rule, up to a budget, and only overspending forces it to shrink?

Give the window a cost and a budget k. The cost counts the elements inside that break the rule, the ones you would have to change. right takes in each element, and while the cost exceeds k, left drops elements; dropping an element that does not break the rule frees nothing, so left may move more than once. The best answer is the longest window whose cost fits.

On nums = [7, 1, 5, 3, 6], keep windows whose values are greater than 4, allowing k = 1 exception. [7, 1, 5] costs 1, for length 3. Taking in 3 raises the cost to 2, so left drops 7, which leaves the cost at 2, then 1, which lowers it to 1. [5, 3, 6] later reaches length 3 too, and no window of 4 ever fits.

Case Scenario

Longest Repeating Character Replacement is a budgeted window over a string: make every letter in the window the same, changing at most k of them. The cheapest fix keeps the most frequent letter, so the cost is length - top, where top is that letter's count. In s = "AABABBA" with k = 1, "AABA" has top = 3 and costs 4 - 3 = 1, so it fits, for length 4.

The direct approach checks every substring: for each start, extend the end one letter at a time, update letter counts, and test whether length - top fits within k. That is about n²/2 substrings, 28 for these seven letters, and each new start throws away the counts the one before it built.