DSA With AI
Week 2 ยท Sliding Window

Longest Repeating Character Replacement

Find the longest window that can become all one character after at most k replacements.

Medium Sliding Window Week 2 Practice runner

Frame the problem

  • The window is contiguous.
  • You may replace at most k characters.
  • The chosen target character is the most frequent character in the current window.
1. Reveal example inputs and outputs

Example 1

Input:

character_replacement("ABAB", 2)

Output:

4

Example 2

Input:

character_replacement("AABABBA", 1)

Output:

4
2. Brute force first

For a fixed window, how do you know the minimum replacements needed to make it uniform?

3. Reveal the insight ladder
  1. Track counts inside the window.
  2. The needed replacements are window_length - max_frequency.
  3. If replacements exceed k, shrink from the left.
  4. The best valid window length is the answer.
4. Dry run before code
  1. s = AABABBA, k = 1.
  2. AABA has max frequency 3 and length 4, so one replacement makes it AAAA.
  3. Longer windows require more than one replacement, so best is 4.
5. Reveal final Python solution 
from collections import defaultdict

def character_replacement(s, k):
    counts = defaultdict(int)
    left = 0
    max_count = 0
    best = 0
    for right, char in enumerate(s):
        counts[char] += 1
        max_count = max(max_count, counts[char])
        while (right - left + 1) - max_count > k:
            counts[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

Complexity: Time O(n), space O(k distinct characters).

Interview narration

  • I keep the window valid by measuring how many characters are not the majority.
  • The max frequency can be maintained monotonically for this problem.
  • Shrinking restores the replacement budget.

Common traps

  • Using the number of distinct characters instead of non-majority count.
  • Recomputing the entire window too often.
  • Forgetting k can be zero.

Follow-up drills

1. Why can max_count be stale?

A stale high max_count may delay shrinking, but it never causes an overestimated answer beyond a window length that was valid when that max_count was observed.

2. How does this differ from longest substring without repeats?

Here repeats are good; the invalid condition is too many non-majority characters, not duplicate existence.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.