Find longest uniform substring after k replacements

Given a string s (ASCII, length up to 2e5) and integer k (0 ≤ k ≤ |s|), return the length of the longest substring that can be turned into all the same character by replacing at most k characters. Constraints and requirements:

• Time O(n), space O(1) amortized (treat alphabet size as constant).
• Explain why a sliding window with a running max‑frequency works and why shrinking the window preserves correctness even as the max frequency may lag.
• Provide examples: s="AABABBA", k=1 ⇒ 4; s="aaabbc", k=2 ⇒ 5; s="abcd", k=1 ⇒ 2.
• Implement in your preferred language and discuss edge cases (k=0, all identical chars, very large n).

Find longest uniform substring after k replacements

Given a string s (ASCII, length up to 2e5) and an integer k (0 <= k <= |s|), return the length of the longest substring that can be turned into all the same character by replacing at most k characters.

Use a sliding window with a running max-frequency: expand the right edge, track the count of each character in the window and the highest single-character frequency seen so far (maxFreq). The number of characters that must be replaced to make the window uniform is windowLength - maxFreq. While that exceeds k, shrink the window from the left. The answer is the largest valid window length.

The window length never decreases because once we find a window of a given size, we only slide it (advancing left in lockstep with right) — so even though maxFreq may lag (we never decrease it when shrinking), the recorded best is preserved. A stale maxFreq can only make the validity check stricter, never looser, so it cannot inflate the answer.

Examples:

• s = "AABABBA", k = 1 => 4
• s = "aaabbc", k = 2 => 5
• s = "abcd", k = 1 => 2

Edge cases to consider: k = 0 (no replacements, longest run of one char), all identical characters (whole string), and very large n (must be O(n)).

Hints

1. Slide a window over s and keep a count of each character inside it.
2. Track the highest single-character frequency in the window (maxFreq). The cost to make the window uniform is windowLength - maxFreq; the window is valid when that cost is <= k.
3. When the window becomes invalid, advance the left pointer. You never need to decrease maxFreq when shrinking — a stale maxFreq only makes the validity test stricter, never looser, so it cannot overcount.