Longest Repeating Character Replacement

Medium

📘 Problem Statement

Given a string s and an integer k, return the length of the longest substring you can get by replacing at most k characters so that all characters in the substring are the same.

🔍 Example

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

Explanation:
We can replace the one 'B' in the middle with an 'A' => "AABA**A**BA" → "AAAA".
Longest repeating substring is "AABA" → replace 'B' with 'A' to get "AAAA" → length 4.

---

Intuition

This is a classic sliding window problem.

We are allowed to change up to k characters to make a substring with all the same letters. The trick is to slide a window over the string and keep track of the most frequent character inside the current window.

To make all letters in the window the same, we only need to change the other characters (i.e., total window size - frequency of most common char in the window). This number should be ≤ k.

✅ Key Insight

For a window [left:right], if:

(right - left + 1) - max_char_count <= k

Then it’s a valid window.

Otherwise, we need to shrink the window from the left.

🛠️ Solution

🧮 Step-by-step Algorithm

We use:

• max_freq: max frequency of any character in current window

• count : dictionary to track frequency of characters in the window

• left : left end of the window

• right : right end of the window (as we iterate)

🧑‍💻 Code

def characterReplacement(self, s: str, k: int) -> int:
    count = defaultdict(int)
    max_freq = 0
    left = 0
    result = 0

    for right in range(len(s)):
        count[s[right]] += 1
        max_freq = max(max_freq, count[s[right]])

        # window length - max_freq gives us number of changes needed
        while (right - left + 1) - max_freq > k:
            count[s[left]] -= 1
            left += 1  # shrink window from left

        result = max(result, right - left + 1)

    return result

🕒 Time Complexity: \(O(n)\) - each character is added/removed from window at most once.

📦 Space Complexity: \(O(1)\) — the character map has at most 26 letters (uppercase English only).