Sliding Window
Window plus a budget
Why it matters
Error-tolerant matching asks how much contiguous data can be normalized under a limited edit budget. Testing every substring repeats counts and becomes quadratic. For "AABABBA" with one allowed replacement, return the longest transformable run, length 4, in O(n) time without enumerating every substring.
Example
Longest Repeating Character Replacement
You may replace at most k characters in s. Return the length of the longest substring that can be made of a single repeating character.
- Input
- s = "AABABBA", k = 1
- Output
- 4
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Longest Repeating Character Replacement
s = "AABABBA", k = 1→4
The baseline, Check every substring, is O(n²) · O(1). The better model below keeps this exact input and removes that bottleneck.
"AABA" in "AABABBA" has three A's, so one replacement makes a valid run of length 4; every length-5 substring needs two changes. Track letter counts for one moving range instead of brute force checking all O(n²) substrings.
In "AABA", A appears 3 times, so length - top is 4 - 3 = 1. Replacing B makes "AAAA", which fits k = 1. Adding the next B makes "AABAB": length 5 with top 3 needs 2 replacements, so remove a character from the left.
Keep counts for the current range as its edges advance. top records the largest frequency reached and does not decrease when the left edge moves. After "AABA" sets top to 3, that stale value can preserve length 4, but it cannot invent a longer answer; any length above 4 would need a new, larger top to fit the same budget.
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.