Longest Repeating Character Replacement

This problem looks scary at first. You are allowed to change some letters. So where do you even start? The interviewer wants to see if you can spot the hidden rule. The rule is simple once you find it. A window is valid when only a few letters need changing. That tiny idea turns a messy problem into a clean sliding window.

🎯 The Problem

You get a string of capital letters and a number k. Here are the rules.

• You can change up to k letters to any other letter.
• Your goal is the longest run where all letters become the same.
• A run that sits next to itself is a substring. A substring is a stretch of characters with nothing skipped.
• Return the length of that longest run.

Take the string "AABABBA" and k as 1. The window "AABA" has three A and one B. Change that one B to A and you get four A in a row. That uses only one change. So the answer is 4.

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

Explanation: Change one B to A to make "AAAA", a run of length 4.

Here is the idea drawn out. Inside any window, you keep the most common letter and change the rest.

🐢 Approach 1: Check Every Window (Brute Force)

The idea in one line: try every possible window and count its changes from scratch.

The idea:

• Look at every start and every end.
• Count the letters inside each window.
• The most common letter stays. The rest are changes.

How it works:

• For each window, find the most common letter.
• The changes needed is window size minus that count.
• If the changes are k or less, the window is allowed.
• Keep the longest allowed window.

Why it is weak:

• You build and count every window from scratch.
• That repeats a huge amount of work.
• The nested passes make it O(n²).

Here is the brute-force code for that idea:

from collections import Counter


def character_replacement(s, k):
    best = 0
    for left in range(len(s)):
        counts = Counter()
        for right in range(left, len(s)):
            counts[s[right]] += 1
            window = right - left + 1
            if window - max(counts.values()) <= k:
                best = max(best, window)
    return best

⚡ Approach 2: Sliding Window With Counts (Best)

The idea in one line: a window is valid when its size minus the most common letter count is at most k, so slide and reuse the counts.

The idea:

• The changes for a window is window size minus the count of the most common letter.
• You keep the most common letter and change everyone else.
• So a window is valid when window size minus the max count is at most k.

How it works:

• Move the right edge forward and add the new letter to a count table.
• A count table remembers how many times each letter showed up.
• If window size minus max count is greater than k, the window needs too many changes.
• Then move the left edge forward and lower that letter’s count.
• That shrinks the window back to a valid size.

Why it is fast:

• The counts are reused, not rebuilt.
• Each letter enters once and leaves once.
• One clean pass, so O(n).

Here is the window growing, then shrinking once it needs too many changes, then growing again.

Steps to Solve

1. Set the left edge at the start. Keep a count table for the letters and a running max count.
2. Move the right edge across the string and add each letter to the count table.
3. Update the max count with the new letter’s count.
4. If window size minus max count is greater than k, move the left edge forward and lower that letter’s count.
5. After each step, record the window size as a possible answer.
6. When the right edge reaches the end, return the largest size you saw.

#include <stdio.h>
#include <string.h>

int characterReplacement(const char *s, int k) {
    int count[26] = {0};   // count of each letter in the window
    int left = 0, best = 0, maxCount = 0;
    int n = (int)strlen(s);
    for (int right = 0; right < n; right++) {
        count[s[right] - 'A']++;                 // add new letter
        if (count[s[right] - 'A'] > maxCount) {
            maxCount = count[s[right] - 'A'];    // track most common
        }
        while ((right - left + 1) - maxCount > k) {  // too many changes
            count[s[left] - 'A']--;              // drop the leftmost
            left++;                              // shrink the window
        }
        if (right - left + 1 > best) best = right - left + 1;
    }
    return best;
}

int main(void) {
    const char *s = "AABABBA";
    printf("%d\n", characterReplacement(s, 1));
    return 0;
}

4

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int characterReplacement(const string &s, int k) {
    int count[26] = {0};   // count of each letter in the window
    int left = 0, best = 0, maxCount = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        count[s[right] - 'A']++;                       // add new letter
        maxCount = max(maxCount, count[s[right] - 'A']); // most common
        while ((right - left + 1) - maxCount > k) {    // too many changes
            count[s[left] - 'A']--;                    // drop leftmost
            left++;                                    // shrink window
        }
        best = max(best, right - left + 1);
    }
    return best;
}

int main() {
    string s = "AABABBA";
    cout << characterReplacement(s, 1) << endl;
    return 0;
}

4

public class CharReplacement {
    public static int characterReplacement(String s, int k) {
        int[] count = new int[26];   // count of each letter in window
        int left = 0, best = 0, maxCount = 0;
        for (int right = 0; right < s.length(); right++) {
            count[s.charAt(right) - 'A']++;            // add new letter
            maxCount = Math.max(maxCount, count[s.charAt(right) - 'A']);
            while ((right - left + 1) - maxCount > k) {  // too many changes
                count[s.charAt(left) - 'A']--;         // drop leftmost
                left++;                                // shrink window
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    public static void main(String[] args) {
        String s = "AABABBA";
        System.out.println(characterReplacement(s, 1));
    }
}

4

def character_replacement(s, k):
    count = {}        # how many times each letter is in the window
    left = 0          # left edge of the window
    best = 0          # longest valid window seen
    max_count = 0     # count of the most common letter in the window
    for right in range(len(s)):
        count[s[right]] = count.get(s[right], 0) + 1   # add new letter
        max_count = max(max_count, count[s[right]])    # track most common
        while (right - left + 1) - max_count > k:      # too many changes
            count[s[left]] -= 1                        # drop leftmost
            left += 1                                  # shrink window
        best = max(best, right - left + 1)             # update best size
    return best


s = "AABABBA"
print(character_replacement(s, 1))

4

function characterReplacement(s, k) {
  const count = {}; // how many times each letter is in the window
  let left = 0;
  let best = 0;
  let maxCount = 0;
  for (let right = 0; right < s.length; right++) {
    count[s[right]] = (count[s[right]] || 0) + 1;  // add new letter
    maxCount = Math.max(maxCount, count[s[right]]); // track most common
    while (right - left + 1 - maxCount > k) {       // too many changes
      count[s[left]]--;                             // drop leftmost
      left++;                                       // shrink window
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

const s = "AABABBA";
console.log(characterReplacement(s, 1));

4

Let us walk through the Python version line by line and see why each line is there.

count = {} is an empty dictionary. It remembers how many times each letter sits inside the window right now. We need these counts to find the most common letter.

left = 0 is the left edge of the window. best = 0 keeps the longest valid window we have found. max_count = 0 is the count of the most common letter inside the window.

for right in range(len(s)): moves the right edge across the string. Each loop pulls in one new letter.

count[s[right]] = count.get(s[right], 0) + 1 adds the new letter to the count table. get returns the old count or zero if the letter is new. Then we add one.

max_count = max(max_count, count[s[right]]) updates the most common count. The new letter might now be the most common one.

while (right - left + 1) - max_count > k: checks the rule. right - left + 1 is the window size. Subtract the most common count and you get the letters you would have to change. If that is more than k, the window is not allowed.

count[s[left]] -= 1 and left += 1 shrink the window from the left. We lower the leftmost letter’s count and move the left edge forward. The while keeps shrinking until the window is allowed again.

best = max(best, right - left + 1) records the window size if it is the biggest so far.

return best gives back the length of the longest valid window.

⏱️ Time and Space Complexity

The brute force counts every window from scratch, so it is slow at O(n²). The sliding window reuses the counts and touches each letter at most twice. So it runs in O(n) time. The memory holds counts for the 26 capital letters, which is a fixed small amount.

🧩 Key Takeaways

• ✅ A window is valid when window size minus the most common letter count is at most k.
• ✅ Keep the most common letter and change the rest. That is the smallest number of changes.
• ✅ Slide the right edge to grow and the left edge to shrink when the window needs too many changes.
• ✅ Reusing the counts instead of recounting takes the time from O(n²) down to O(n).
• ✅ Talk through the brute force first, then explain the valid-window rule. That shows your thinking.

🚀 What’s Next?

• Longest Substring Without Repeating Characters
• Minimum Window Substring