Skip to main content
DSA patterns

Longest Repeating Character Replacement

mediumSliding windowGoogleMetaUber

Problem statement

You are given a string s made only of uppercase English letters, and a budget k. You may pick up to k characters anywhere in the string and change each one to any other uppercase letter.

Return the length of the longest substring you can turn into a single repeated letter, using at most k of those changes.

Examples

Example 1

Input: s = "ABAB", k = 2

Output: 4

Explanation: Change both As to B (or both Bs to A) and the whole

Example 2

Input: s = "AABABBA", k = 1

Output: 4

Explanation: Change the single A in the middle to B, giving

Hints

Hint 1: To turn any substring into one repeated letter, you only need to change every character that isn't already that substring's most common letter — so pick the letter that's already most common.

Approach

Optimal: Sliding window, no shrink

Intuition

Here's the trick: you don't actually need the window to shrink back to being valid at every step. You only care about the longest window you ever manage to build, and a window can never grow past the best one already found unless it becomes at least that good again. So instead of shrinking with a while loop, just check once: if the window is too expensive, slide it by exactly one step (drop the oldest letter, move left forward by one) and move on. The window's size then either grows or stays exactly the same size it was before — it can never shrink from where it "peaked" — so tracking right - left + 1 after this single check gives the correct answer at the end.

The key detail: the running maxCount you keep is a high-water mark. It records the highest letter frequency ever seen while the window was expanding — it never decreases, even after letters are dropped. That sounds wrong, but it isn't: an outdated maxCount can only make the check `(window) - maxCount

Note

k*stricter* than it truly needs to be, which can only stop the window from growing when it technically could have grown a little more — and by the time a real, longer valid window exists,maxCount` will have already grown to match it. It never lets an invalid window through.

Steps

  1. Start with left = 0, an empty count array, maxCount = 0, and best = 0.
  2. For each right from 0 to n - 1:
    1. Add s[right] to the count array.
    2. Update maxCount to the larger of itself and the new count for s[right].
    3. If (right - left + 1) - maxCount > k, the window is too expensive: drop s[left] from the count array and move left forward by one (only once — no loop).
    4. Update best with right - left + 1.
  3. Return best.

Dry run

s = "AABABBA", k = 1

right char freq (A, B) maxCount window before check valid? action window size best
0 A A:1 1 1 yes — 1 1
1 A A:2 2 2 yes — 2 2
2 B A:2, B:1 2 3 yes — 3 3
3 A A:3, B:1 3 4 yes — 4 4
4 B A:3, B:2 3 5 no (5-3=2>1) drop s[0]=A, left→1 4 4
5 B A:2, B:3 3 5 no (5-3=2>1) drop s[1]=A, left→2 4 4
6 A A:2, B:2 3 (stale) 5 no (5-3=2>1) drop s[2]=B, left→3 4 4

maxCount freezes at 3 from step right = 3 onward, even though the count of A in the current window later drops to 2 — that's the "high-water mark" from the Intuition. The window size after each step never exceeds the best already found, so the final best = 4 is correct.

Edge cases: k = 0 means no changes at all, so the answer is the length of the longest run of one repeated letter already in s. k >= s.length means every letter can be changed, so the answer is simply len(s).

flowchart LR A[Add s at right to the counts] --> B[Update maxCount with the new count] B --> C{window length - maxCount > k?} C -- yes --> D[Drop s at left, move left forward by one] C -- no --> E[Record window length if it's the best so far] D --> E E --> F[Move right forward by one] F --> A

Complexity

Time O(n) - each index enters and leaves the window at most once, and every step does a fixed, constant amount of work (one count update, one comparison to update the running maximum, and at most one letter dropped). There's no repeated scan of the 26 counts, which is what made the Better approach's constant factor larger.

Space O(1) - the same 26-slot count array.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        counts = [0] * 26
        left = 0
        max_count = 0
        best = 0
        for right in range(len(s)):
            idx = ord(s[right]) - ord('A')
            counts[idx] += 1
            max_count = max(max_count, counts[idx])
            if (right - left + 1) - max_count > k:
                counts[ord(s[left]) - ord('A')] -= 1
                left += 1
            best = max(best, right - left + 1)
        return best


if __name__ == "__main__":
    print(Solution().characterReplacement("ABAB", 2))       # 4
    print(Solution().characterReplacement("AABABBA", 1))    # 4
RecapThe whole problem in a few lines, for the night before
  • Spot it: longest substring that can become one repeated letter with at most k changes
  • Idea: variable window; it is valid while window length - count of its most frequent letter <= k; otherwise move the left edge
  • Cost: O(n) time, O(1) space (26 letters)
  • Trap: the max frequency does not need to be lowered when the window shrinks; the answer only grows when a new higher max is found

Interview follow-ups

  • What if k is at least as large as the length of s?

    Then every letter can be changed if needed, so the whole string always qualifies and the answer is simply len(s). The algorithm already handles this correctly without a special case: the window never needs to shrink, because (right - left + 1) - maxCount can never exceed k when k is that large.

  • Return the actual substring, not just its length.

    Track bestLeft alongside best and update both together whenever you find a new longest window: bestLeft = left. At the end, the answer substring is s[bestLeft : bestLeft + best]. This works even with the "no shrink" trick, because left at the moment you record a new best is exactly the left edge of that window.

  • The string arrives as a stream and doesn't fit in memory. How would you adapt this?

    The algorithm already only looks at one character at a time and a 26-slot count array — it never needs the whole string in memory. Keep left, right, maxCount, best and the counts as running state, process each new character as it arrives, and drop the count for s[left] when the window slides. Memory stays O(alphabet size), completely independent of how long the stream runs.

Frequently asked questions

It sounds risky, but it isn't. maxCount is only ever used to decide whether the current window still fits the budget. Letting it stay too high just means the check is a little too strict, which can only make the algorithm slide the window forward instead of letting it grow — it never lets an actually-invalid window count toward the answer. And because the true answer only comes from letters that are truly repeated close together, maxCount will have already risen to the correct value by the time a genuinely longer window appears.

The re-scan itself only looks at 26 numbers, which is a constant, not something that grows with n. So each shrink step costs O(1), and there are at most n shrink steps total (the left pointer moves forward at most n times over the whole run). That keeps the total work at O(26·n), which simplifies to O(n) — just with a larger constant factor than the Optimal approach, which is why it's presented as a distinct, "correct but not yet polished" step.

It's the same shape as tolerating a run of flaky results. Picture a stream of health-check outcomes, U for up and D for down, and a budget of k results you're willing to treat as "probably fine" (say, a known blip). "What's the longest stretch I can call continuously healthy, allowing up to k blips?" is exactly this problem, with two symbols instead of 26.

Swap the fixed 26-slot array for a hash map from character to count. The algorithm and its complexity stay the same — O(n) time, O(distinct characters) space — but a hash map's per-operation cost is O(1) only on average, not guaranteed, the way a small fixed array's is.