Longest Repeating Character Replacement [Medium] — Max-Freq Window

Problem Statement

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

Input: s="ABAB", k=2 → Output: 4
Input: s="AABABBA", k=1 → Output: 4

Intuition

Sliding window. Keep maxFreq = frequency of the most common char in window. Window is valid when window_size - maxFreq <= k (we only need to replace the non-dominant characters). Expand right; shrink left when invalid.

Key insight: We never shrink maxFreq down even if a char leaves the window — this ensures we only look for longer windows (valid optimization).

Solutions

C++

int characterReplacement(string s, int k) {
    int freq[26]={}, maxFreq=0, left=0, ans=0;
    for(int r=0;r<s.size();r++){
        maxFreq=max(maxFreq,++freq[s[r]-'A']);
        while(r-left+1-maxFreq>k) freq[s[left++]-'A']--;
        ans=max(ans,r-left+1);
    }
    return ans;
}

Java

public int characterReplacement(String s, int k) {
    int[] freq=new int[26]; int maxFreq=0,left=0,ans=0;
    for(int r=0;r<s.length();r++){
        maxFreq=Math.max(maxFreq,++freq[s.charAt(r)-'A']);
        while(r-left+1-maxFreq>k) freq[s.charAt(left++)-'A']--;
        ans=Math.max(ans,r-left+1);
    }
    return ans;
}

JavaScript

var characterReplacement = function(s, k) {
    const freq=new Array(26).fill(0); let maxFreq=0,left=0,ans=0;
    for(let r=0;r<s.length;r++){
        maxFreq=Math.max(maxFreq,++freq[s.charCodeAt(r)-65]);
        while(r-left+1-maxFreq>k) freq[s.charCodeAt(left++)-65]--;
        ans=Math.max(ans,r-left+1);
    }
    return ans;
};

Python

def characterReplacement(s: str, k: int) -> int:
    freq = [0] * 26
    max_freq = left = ans = 0
    for r, c in enumerate(s):
        freq[ord(c)-65] += 1
        max_freq = max(max_freq, freq[ord(c)-65])
        while (r - left + 1) - max_freq > k:
            freq[ord(s[left])-65] -= 1
            left += 1
        ans = max(ans, r - left + 1)
    return ans

Complexity

Time: O(n × 26) worst → O(n) since alphabet is constant
Space: O(26) = O(1)