Algorithm

Longest Repeating Character Replacement

Sliding Window Pattern

Longest Repeating Character Replacement

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.

CONSTRAINTS
  • 1 <= s.length <= 10⁵
  • s consists of only uppercase English letters
  • 0 <= k <= s.length
EXAMPLE 1
Input: s = "ABAB", k = 2
Output: 4
Replace the two "A"s (or two "B"s) to get "BBBB" or "AAAA". Window [A,B,A,B] has length 4, maxFreq 2 (either A or B), replacements needed = 4-2 = 2 <= k=2. Valid.
EXAMPLE 2
Input: s = "AABABBA", k = 1
Output: 4
Best window is "AABA" or "ABBA" of length 4. In "AABA": maxFreq(A)=3, replacements = 4-3 = 1 <= k=1. Valid.
EXAMPLE 3
Input: s = "AAAA", k = 0
Output: 4
No replacements allowed, but all characters are already the same. The entire string is valid with 0 replacements.
Are the characters always uppercase English letters?
Yes. Only uppercase A-Z. Use a fixed array of size 26 indexed by character code for efficiency.
Can k be zero?
Yes. When k=0, no replacements are allowed. The answer is the longest run of a single repeated character in the string.
Can I replace a character with any letter?
Yes. Any character can be replaced with any other uppercase English letter. The optimal choice is always to match the most frequent character in the window.

You want the longest window you can make uniform (all one letter) by changing at most k of its characters. The smart move inside any window is fixed: leave the letter that already appears most often, and spend replacements turning the rest into it. So a window of length L whose most frequent letter appears maxFreq times needs L - maxFreq replacements. The window is affordable exactly when:

Key InsightL − maxFreq ≤ k. The count of characters that are not the window's most common letter must fit inside the replacement budget k.

That is the same "at most k violations inside the window" shape as Max Consecutive Ones III — here a "violation" is a character that isn't the window's majority — so it is again the longest-window Variable Sliding Window.

Why brute force is slow

Checking every substring and counting letters to find its majority is O(N²) or worse — the usual overlap waste, recomputing counts that barely changed from the previous window.

Expand, and slide when unaffordable

Keep a 26-letter count of the window and maxFreq, the highest single count seen. Extend right; when L - maxFreq exceeds k the window is unaffordable, so release one character on the left. Record the width.

python
from collections import defaultdict
def characterReplacement(s, k):
    count = defaultdict(int)
    left = 0
    max_freq = 0
    best = 0
    for right in range(len(s)):
        count[s[right]] += 1
        max_freq = max(max_freq, count[s[right]])
        if (right - left + 1) - max_freq > k:   # unaffordable - drop one on the left
            count[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best
Crucial Notetwo things here look like bugs but are deliberate. First, we never lower max_freq even when a character leaves the window — a stale, too-high max_freq can only make L - max_freq look smaller (more affordable), so it can never trick us into accepting a window that is genuinely too expensive. Second, we use if, not while: because we only ever want the longest window, we let it slide (drop one on the left, gain one on the right) rather than truly shrink. The window's size never decreases; it only grows when a genuinely better window exists — which only happens when some letter reaches a new, higher maxFreq. That is exactly why leaving max_freq stale is safe.
Worked Example:"AABABBA", k = 1
- right=0 'A': count{A:1}, maxFreq 1, L=1, 1−1=0 ≤ 1. best 1.
- right=1 'A': {A:2}, maxFreq 2, L=2, 0 ≤ 1. best 2.
- right=2 'B': {A:2,B:1}, maxFreq 2, L=3, 3−2=1 ≤ 1. best 3.
- right=3 'A': {A:3,B:1}, maxFreq 3, L=4, 4−3=1 ≤ 1. best 4.
- right=4 'B': {A:3,B:2}, maxFreq 3, L=5, 5−3=2 > 1 — slide: drop A at left, {A:2,B:2}, left=1. best stays 4.
- right=5 'B': {A:1,B:3}, maxFreq 3, L=5, 5−3=2 > 1 — slide: drop A, {A:... }, left=2. best 4.
- right=6 'A': maxFreq 3, still 2 > 1 — slide, left=3. best 4.
- Answer: 4 (e.g. "AABA", one B changed to A).
How it maps onto the pattern

The four slots: (a) invalid = (windowLen − maxFreq) > k; (b) expand bumps one letter's count and maybe maxFreq; (c) shrinking decrements the outgoing letter's count; (d) record = max width. The transferable idea beyond the pattern is the validity test itself — "the window costs L − maxFreq to make uniform" — which is the kind of cheap, incrementally-maintained quantity that makes a window applicable. When a problem says "you may change / remove / tolerate up to k things, find the longest stretch", look for a per-window cost you can keep updated as the edges move; that cost becomes the invalid rule.

Interactive Strategy Visualization

Character Replacement

k=1
Window Logic
A
0
A
1
B
2
A
3
B
4
B
5
A
6
Max Frequency
2
Flips Used
0 / 1
Window Size
2

Constraint Insight

The cost of making a window uniform is len - maxFreq. As long as this cost is ≤ k, we can replace the minority characters and form a valid repeating substring.

Step-by-Step Logic

Step 1: Window [AA]. All same. MaxFreq: 2. Len: 2. Valid.

O(N²) Brute Force
→
O(N) Variable Sliding Window