Longest Repeating Character Replacement

Problem

Given a string and an integer k, find the length of the longest substring that can be made entirely one character by replacing at most k characters.

Input:  s = "AABABBA", k = 1
Output: 4   ("AABA" -> "AAAA")

Python Solution

def character_replacement(s, k):
    counts = {}
    left = 0
    max_count = 0
    best = 0
    for right, ch in enumerate(s):
        counts[ch] = counts.get(ch, 0) + 1
        max_count = max(max_count, counts[ch])
        window_size = right - left + 1
        if window_size - max_count > k:
            counts[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

C++ Solution

int characterReplacement(string s, int k) {
    unordered_map<char, int> counts;
    int left = 0, maxCount = 0, best = 0;
    for (int right = 0; right < s.size(); right++) {
        counts[s[right]]++;
        maxCount = max(maxCount, counts[s[right]]);
        if ((right - left + 1) - maxCount > k) {
            counts[s[left]]--;
            left++;
        }
        best = max(best, right - left + 1);
    }
    return best;
}

Java Solution

class Solution {
    public int characterReplacement(String s, int k) {
        int[] counts = new int[26];
        int left = 0, maxCount = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            counts[s.charAt(right) - 'A']++;
            maxCount = Math.max(maxCount, counts[s.charAt(right) - 'A']);
            if ((right - left + 1) - maxCount > k) {
                counts[s.charAt(left) - 'A']--;
                left++;
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

Complexity

Time: O(n) — the right pointer scans once, and the left pointer only ever moves forward. Space: O(1) — a fixed 26-slot frequency array for uppercase letters.