DSA problem

Longest Repeating Character Replacement

MediumSliding Window - Dynamic SizePattern: Variable-Size Sliding Windowtop300GoogleAmazonFacebookMicrosoftUber

You are given a string s consisting of uppercase English letters and an integer k. You may choose any character in the string and change it to any other uppercase letter, and you may perform this operation at most k times. Return the length of the longest substring containing the same letter you can obtain after performing those replacements.

The challenge is that the replacements are a budget, not a fixed plan. We are not told which characters to change; instead we want to find a window where, after spending at most k replacements, every character becomes identical. This means we need a way to evaluate windows against a budget rather than against an exact match.

For any window, the cheapest way to make all characters equal is to keep the most frequent character and replace all the others. The number of replacements required is therefore the window length minus the count of the most frequent character in that window. A window is feasible exactly when that quantity is at most k.

The intuition for the sliding window is to expand the right boundary greedily and track character frequencies. Whenever windowLength - maxFrequency exceeds k, the window is infeasible, so we shrink it from the left by one. A subtle but powerful detail: we never need to decrease the tracked maximum frequency, because the answer can only grow when a larger valid window appears, so keeping a stale maximum still yields the correct final result in a single linear pass.

Examples

Constraints

• 1 <= s.length <= 10^5
• s consists of only uppercase English letters.
• 0 <= k <= s.length

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

sliding-windowstringhash-tabletwo-pointers

Browse all DSA problems