plaintext
max_length = 0
for i from 0 to length(s):
    for j from i to length(s):
        substring = s[i...j]
        freq_map = count_chars(substring)
        max_f = max_value(freq_map)
        if (length(substring) - max_f) <= k:
            max_length = max(max_length, length(substring))

Complexity Analysis:

• Time Complexity: $O(N^3)$. There are $O(N^2)$ substrings. For each substring, iterating to count frequencies takes $O(N)$. This is highly inefficient.
• Space Complexity: $O(1)$ (or $O(26)$ for the frequency map).

Why it fails: With constraints allowing s.length up to $10^5$, an $O(N^3)$ or even $O(N^2)$ solution will immediately trigger a Time Limit Exceeded (TLE). We need a linear or near-linear approach.

Core Insight for Longest Repeating Character Replacement

The key to optimizing the brute force approach lies in how we validate the substring. A substring is valid if the number of characters that are not the dominant character is less than or equal to k.

Mathematically, the condition is: $\text{Window Length} - \text{Count of Most Frequent Char} \le k$

Instead of recalculating frequencies for every new substring, we can maintain a running frequency count as we slide a window across the string.

1. Expand (Right Pointer): We extend the window to the right, adding the new character to our frequency map. This potentially increases the max_freq and the window length.
2. Constraint Check: We check if the current window is valid using the formula above.
3. Contract (Left Pointer): If the window becomes invalid (i.e., we need more than k replacements), we shrink the window from the left. This reduces the window length and updates the frequency map, restoring validity.

Visual Description: Imagine the window as an elastic band stretching over the string. The right end pulls forward to capture more characters. As it stretches, we track the count of the "dominant" character inside. If the number of "non-dominant" characters (the holes in our pattern) exceeds k, the left end of the elastic band snaps forward, shrinking the window until the number of holes is $\le k$ again.

Execution Flow

Consider s = "AABABBA", k = 1.

1. Start: left=0, right=0, max_freq=0.
2. Index 0 ('A'): Window "A". max_freq (A) = 1. Valid ($1-1 \le 1$). Length 1.
3. Index 1 ('A'): Window "AA". max_freq (A) = 2. Valid ($2-2 \le 1$). Length 2.
4. Index 2 ('B'): Window "AAB". max_freq (A) = 2. Valid ($3-2 \le 1$). Length 3.
5. Index 3 ('A'): Window "AABA". max_freq (A) = 3. Valid ($4-3 \le 1$). Length 4.
6. Index 4 ('B'): Window "AABAB". max_freq (A) = 3.
   • Check: Length 5. $5 - 3 = 2$.
   • $2 > k$ (1). Invalid.
   • Shrink: Remove s[0] ('A'). left becomes 1. Window is "ABAB".
7. Index 5 ('B'): Window "ABABB". max_freq (B) = 3.
   • Check: Length 5. $5 - 3 = 2$.
   • $2 > k$. Invalid.
   • Shrink: Remove s[1] ('A'). left becomes 2. Window is "BABB".
8. Index 6 ('A'): Window "BABBA". max_freq (B) = 3.
   • Check: Length 5. $5 - 3 = 2$.
   • $2 > k$. Invalid.
   • Shrink: Remove s[2] ('B'). left becomes 3. Window is "ABBA".

Max length recorded was 4.

Proof of Correctness

The algorithm is correct because the sliding window invariant is maintained at every step.

1. Invariant: For any window ending at right, the left pointer is positioned at the smallest index such that the window s[left...right] is valid (or, in the optimized version, left moves just enough to maintain the maximum window size seen so far).
2. Coverage: The right pointer traverses every possible end position of a substring.
3. Optimality: By expanding as much as possible and only shrinking when strictly necessary to satisfy the k constraint, we ensure that if a valid window of length L exists, the algorithm will reach a state where right - left + 1 == L.

Reference Implementation

C++ Solution for LeetCode 424

cpp
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int characterReplacement(string s, int k) {
        vector<int> count(26, 0);
        int left = 0;
        int maxCount = 0;
        int maxLength = 0;

        for (int right = 0; right < s.length(); ++right) {
            // Add current character to window
            count[s[right] - 'A']++;
            
            // Update the count of the most frequent character in the current window
            maxCount = max(maxCount, count[s[right] - 'A']);

            // Current window length is (right - left + 1)
            // Replacements needed = Window Length - maxCount
            // If replacements needed > k, shrink window
            if ((right - left + 1) - maxCount > k) {
                count[s[left] - 'A']--;
                left++;
            }

            // Update global maximum length
            maxLength = max(maxLength, right - left + 1);
        }

        return maxLength;
    }
};

Java Solution for LeetCode 424

java
class Solution {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int left = 0;
        int maxCount = 0;
        int maxLength = 0;

        for (int right = 0; right < s.length(); right++) {
            // Add current character to window
            char currentChar = s.charAt(right);
            count[currentChar - 'A']++;
            
            // Track the most frequent character count in the current window history
            maxCount = Math.max(maxCount, count[currentChar - 'A']);

            // If the window is invalid (replacements needed > k), slide left pointer
            // Note: We use 'if' instead of 'while' here because we only need to 
            // shift the window, not strictly shrink it to minimum valid size,
            // to find the maximum length.
            if ((right - left + 1) - maxCount > k) {
                count[s.charAt(left) - 'A']--;
                left++;
            }

            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }
}

Python Solution for LeetCode 424

python
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = {}
        left = 0
        max_freq = 0
        max_length = 0
        
        for right in range(len(s)):
            # Add current char to frequency map
            char = s[right]
            count[char] = count.get(char, 0) + 1
            
            # Update max frequency seen in the current window
            max_freq = max(max_freq, count[char])
            
            # Check validity: length - max_freq <= k
            # If invalid, shrink from the left
            if (right - left + 1) - max_freq > k:
                count[s[left]] -= 1
                left += 1
            
            # Update result
            max_length = max(max_length, right - left + 1)
            
        return max_length