Given a string and an integer k, find the length of the longest substring where all characters can be made identical by replacing at most k characters.

Problem Statement

Input: A string s of uppercase English letters and an integer k
Output: Length of the longest substring achievable after at most k replacements
Constraints: 1 <= s.length <= 10^5, 0 <= k <= s.length

Example:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace one 'B' to get "AAAA" (substring from index 0-3)

The Key Insight

A window is valid when the number of characters to replace (window size minus most frequent character count) doesn't exceed k.

This one rule is the entire algorithm. For any window, if we know the most frequent character's count, the minimum replacements needed is just window_size - max_frequency. When this exceeds k, the window is too large.

Why Sliding Window?

Instead of checking every possible substring (which would be O(n²)), we use a sliding window:

• Expand the window by adding characters from the right
• Track character frequencies and the maximum frequency seen
• When the window becomes invalid (needs > k replacements), shrink from the left
• Remember the largest valid window we've seen

The Solution

def character_replacement(s, k):
    """
    Find longest substring with same letter after k replacements.
    
    Time: O(n) - single pass through string
    Space: O(1) - at most 26 characters in counts dict
    """
    counts = {}
    left = 0
    max_freq = 0
    max_length = 0
    
    for right in range(len(s)):
        char = s[right]
        counts[char] = 1 + counts.get(char, 0)
        max_freq = max(max_freq, counts[char])
        
        # Window is invalid if replacements needed > k
        while (right - left + 1) - max_freq > k:
            counts[s[left]] -= 1
            left += 1
        
        max_length = max(max_length, right - left + 1)
    
    return max_length

Step-by-Step Walkthrough

Let's trace through s = "AABABBA" with k = 1:

Step 1-4: Window expands, all valid

Window: "A" → max_freq=1, need 0 replacements ✓ (length 1)
Window: "AA" → max_freq=2, need 0 replacements ✓ (length 2)
Window: "AAB" → max_freq=2, need 1 replacement ✓ (length 3)
Window: "AABA" → max_freq=3, need 1 replacement ✓ (length 4) ← MAXIMUM

Step 5: Window becomes invalid

Window: "AABAB" → max_freq=3, need 2 replacements ✗ (exceeds k=1)
Action: Shrink from left, remove 'A'

Step 6: Still invalid after one shrink

Window: "ABAB" → max_freq=2, need 2 replacements ✗
Action: Shrink again, remove 'A'

Step 7: Valid again

Window: "BAB" → max_freq=2, need 1 replacement ✓

Step 8-11: Continue sliding

Window: "BABB" → max_freq=3, need 1 replacement ✓
Window: "BABBA" → max_freq=3, need 2 replacements ✗ → shrink
Window: "ABBA" → max_freq=2, need 2 replacements ✗ → shrink
Window: "BBA" → max_freq=2, need 1 replacement ✓

Result: The longest valid window is 4 (substring "AABA" where we replace one 'B' with 'A').

Why This Works

The algorithm never misses the optimal answer because:

1. We try every possible ending position (right pointer scans entire string)
2. For each ending position, we find the longest valid window ending there
3. Invalid windows are always shrunk to become valid again
4. We track the maximum across all valid windows

Complexity Analysis

Time: O(n) - Each character is visited at most twice (once by right pointer, once by left)
Space: O(1) - At most 26 characters in the frequency map (fixed alphabet size)

---

Quick recap: Use a sliding window to track the longest valid substring. A window is valid when window_size - max_frequency ≤ k. Expand right, shrink left when invalid, track the maximum. Time complexity is O(n) with constant space.