LeetMotion
You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.
Return the length of the longest substring containing the same letter you can get after performing the above operations.
maxf is valid when W - maxf ≤ k. The W - maxf characters are the "minority" chars you'd replace with at most k operations.W - maxf > k), advance L to shrink it. Track maxf as you go — it only needs to increase for res to grow.maxf. So if maxf doesn't increase after adding a new character, we just slide L forward without reducing maxf — the window size stays the same, preserving our best candidate.In network engineering, a stream of data packets may contain occasional corrupt packets. If you can correct at most k corrupt packets in any contiguous window, what is the longest uninterrupted "clean" segment you can guarantee? This is exactly the character replacement problem — find the longest window where the number of "minority" elements (corrupt packets) does not exceed k. The sliding window approach solves this in O(n), critical for real-time network diagnostics.
The key insight: the window is valid when (window_size - maxf) ≤ k. We expand R greedily and only shrink L when the window becomes invalid.
count = {}, l = 0, maxf = 0, res = 0.s[r] to count. Update maxf = max(maxf, count[s[r]]).(r - l + 1) - maxf > k: remove s[l] from count, advance l.res = max(res, r - l + 1).res after scanning all positions.The window never truly shrinks in size — when invalid, L advances by 1 to match R's advance. This keeps the window at its best known size, ensuring O(n) time.
Discussion
…