← DSA Atlas
Dedicated problem page · #424

Longest Repeating Character Replacement

MediumSliding WindowVariable-size window constrained by replaceable slotsSliding window + frequency count
Solve on LeetCode ↗
424
MediumSliding WindowSliding window + frequency countVariable-size window constrained by replaceable slots

Longest Repeating Character Replacement

Given a string s of uppercase English letters and an integer k, you may replace at most k characters with any uppercase letter. Return the length of the longest substring containing a single repeated letter you can produce after those replacements.

Open official problem prompt ↗
In plain English

Find the longest window that can be turned into all-identical letters using no more than k replacements.

Picture it like this

You have k blank tiles in a word game; the longest run you can make uniform is the run where only k tiles differ from its most common letter.

Example
Input
s = "AABABBA", k = 1
Output
4
Why
Replacing one character in "AABA" (or "ABBA") yields four identical letters, e.g. "AAAA".
Constraints
1 <= s.length <= 10^5s consists of only uppercase English letters0 <= k <= s.length
Pattern lesson

See the pattern, then code

Variable-size window constrained by replaceable slots
Recognition clue

Longest substring where you may 'fix' up to k mismatches — the window is valid while (window length - count of its most frequent letter) <= k.

↗
Sliding Window

Longest, shortest, maximum, or minimum contiguous subarray or substring.. In any window, the characters you must replace are all the non-majority ones. If that number of replacements exceeds k, the window is invalid, so shrink from the left.

New words, made simpleKnow these before the algorithm
max_freq
The count of the most frequent single character within the current window.
Replacements needed
Window length minus max_freq — the characters that would have to change.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Try every substring

Quadratic scanning of windows is too slow for n up to 10^5.

For each window compute its majority letter and the replacements needed.

Time O(n^2 * 26)Space O(1)
Best choiceSliding window with running max frequency

One linear pass with 26 counters; the window only grows or slides, never rescanned.

Keep counts; a window is valid while length - max_freq <= k; never shrink below the best-known width.

Time O(n)Space O(1)
The rule we keep true

Invariant

Every window recorded as an answer satisfies (window length - count of its most frequent letter) <= k, so it is achievable with at most k replacements.

Why this is correct

Reasoning

The optimal window keeps its majority letter and replaces the rest, so the number of edits is exactly length - max_freq. The window width never decreases: because max_freq is monotonic in the sense used here, once we reach a width we only slide it forward, and the final best is the largest width for which the constraint ever held.

The algorithm in three movesSay these aloud before coding
1Extend the window one character to the right and update its frequency

window 'AABA' len 4, max_freq(A)=3

2Track the highest single-character frequency seen in the window (max_freq)

4 - 3 = 1 <= k=1 -> valid

3While window_len - max_freq > k, shrink from the left

best = 4

4Record the largest valid window length

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
A0
A1
B2
A3
B4
B5
A6
1 · Reads[0..3]
2 · AskEdits needed = 4 - max_freq?
3 · Update statecount A=3,B=1, max_freq=3
4 · Result4 - 3 = 1 <= 1, best = 4
Key takeaway

Window AABA has three A's; replacing its single B (1 <= k) makes four equal letters.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-6State setup

    count holds per-letter frequencies in the window; left is the window start; max_freq tracks the dominant letter's count.

  2. 2
    Lines 7-9Grow and update max

    Add the new character and refresh max_freq for the current window.

  3. 3
    Lines 10-12Shrink when infeasible

    If replacements needed exceed k, drop characters from the left until the window is valid again.

  4. 4
    Lines 13Record best

    The current window width is a candidate answer.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • k = 0 reduces to the longest run of one identical letter
  • k >= length means the whole string is answerable, return length
  • All identical letters returns the full length
  • Single character returns 1
!

Common beginner mistakes

  • Recomputing max_freq by scanning all 26 counts inside the shrink loop (unneeded; a stale-but-monotone max_freq still yields the correct answer)
  • Shrinking with an if instead of the window never contracting below best width — using while here is fine but the classic version keeps a non-shrinking window
  • Forgetting to decrement the left character's count when sliding
Check your understanding

Why is it safe to never decrease max_freq even after characters leave the window?

More in Sliding Window

#3Longest Substring Without Repeating CharactersVariable-size sliding window with last-seen index#76Minimum Window SubstringShrinkable window covering a multiset requirement#30Substring with Concatenation of All WordsWord-aligned sliding window over fixed-length tokens#121Best Time to Buy and Sell StockRunning minimum with best forward difference#209Minimum Size Subarray SumShrinking window on a sum threshold#239Sliding Window MaximumMonotonic decreasing deque