Skip to content

Practice Longest Repeating Character Replacement

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Medium#424
LeetCode Problem

Longest Repeating Character Replacement

Problem Statement

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.

Source: Longest Repeating Character Replacement on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

Input
s = "ABAB", k = 2
Output
4

# Example 2

Input
s = "AABABBA", k = 1
Output
4

Constraints

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

How to solve Longest Repeating Character Replacement

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

A window is fixable with k changes exactly when its length minus its most frequent letter's count is at most k. Once a window length is achieved there is no reason to shrink below it, so the window only slides or grows, and the running maximum frequency never needs to decrease.

Why brute force is not enough

Enumerate every substring and count its 26 letters to test whether length minus the top frequency is at most k. That is O(26 n^2) work; with s.length up to 10^5 it is on the order of 10^11 operations.

Approach

  1. Keep a 26-entry frequency table for the letters inside a window defined by a left and a right index, plus a running record of the largest frequency ever observed.
  2. Advance the right end one character at a time, incrementing that letter's count and updating the running maximum if it grew.
  3. If the window length minus the running maximum exceeds k, advance the left end and decrement the departing letter's count without recomputing the maximum; a stale, larger maximum only blocks growth until a genuinely better window appears.
  4. The window length at the end is the answer. The invariant is that the window length equals the best length found so far, because the window never shrinks and grows only when a valid longer window exists.

Walkthrough of Example 2

s = "AABABBA", k = 1 → 4

  1. Indices 0 and 1 add two As; the window AA has length 2, and 2 minus 2 is 0, within k = 1, so the best is 2.
  2. Adding B at index 2 gives AAB, length 3, maximum frequency 2, and 3 minus 2 is 1, still allowed; best becomes 3.
  3. Adding A at index 3 gives AABA, length 4, maximum frequency 3, and 4 minus 3 is 1; best becomes 4.
  4. Adding B at index 4 gives length 5 with maximum 3, and 5 minus 3 is 2, which exceeds k, so the left end moves past index 0 and the window is ABAB of length 4.
  5. Each later step adds one letter and forces one removal, so the window stays at length 4 to the end, and 4 is the expected output.

Time and space

Time O(n) · Space O(1). Each index enters and leaves the window at most once, and the frequency table has 26 fixed entries, where n is the length of s.

Interview pitfalls

  • Rescanning the whole window to recompute the maximum after every move pushes toward quadratic time; keep the historical maximum or scan only the 26 counts.
  • Returning the maximum frequency plus k instead of the window length, which overshoots when k exceeds the number of other characters.
  • Forgetting the k equals 0 case, where the answer is simply the longest run of a single letter.
  • Lowering the running maximum to the departed letter's count when the left end moves, which can wrongly shrink the window.

Follow-up questions interviewers ask

  • Would the historical-maximum trick still be correct for an arbitrary Unicode alphabet, and what would the per-step cost become?
  • Can you return the actual substring and the positions that should be changed, not just its length?

Related LeetCode Problems

Practice more problems similar to Longest Repeating Character Replacement.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.