L8. Longest Repeating Character Replacement | 2 Pointers and Sliding Window

This chapter covers the optimal solution to the Longest Repeating Character Replacement problem using the Two-Pointer and Sliding Window pattern. We will systematically evolve our approach from a naive $O(N^2)$ brute-force algorithm to an optimized $O(N)$ linear-time solution by analyzing window constraints and maintaining maximum frequency tracking.

1. Problem Statement & Core Objective

You are given a string s consisting solely of uppercase English letters and an integer k.

• Operation: You are allowed to pick up to $k$ characters anywhere in the string and convert them to any other uppercase letter.
• Goal: Find the length of the longest contiguous substring containing all identical characters after performing at most $k$ replacements.

Real-Life Analogy: The Editing Budget

Imagine you are proofreading a printing press ribbon of letters. You have an erasure and ink correction budget of $k$ operations. You want to scan across the ribbon to frame the longest possible banner where almost all letters match, using your $k$ corrections to fix any stray mismatching letters. If a stray letter count exceeds $k$, your budget is busted, and you must shift your viewing frame.

2. Naive Brute-Force Approach ($O(N^2)$)

The Concept

The most straightforward approach is to generate every possible substring, count the frequencies of all characters within that substring, and determine how many characters need to be changed.

To minimize conversions within any given substring, you should never change the character that appears most frequently. Instead, you change all other characters.

Conversion Formula

For any arbitrary substring:

If this required number of conversions is less than or equal to $k$, the substring is valid.

Naive Pseudocode

max_length = 0
for i in range(len(s)):
    hash_map = [0] * 26
    max_f = 0
    for j in range(i, len(s)):
        char_idx = ord(s[j]) - ord('A')
        hash_map[char_idx] += 1
        max_f = max(max_f, hash_map[char_idx])
        
        length = j - i + 1
        changes_required = length - max_f
        
        if changes_required <= k:
            max_length = max(max_length, length)
        else:
            break # Exceeds budget, stop extending this starting point

Complexity Analysis

• Time Complexity: $O(N^2)$ because we iterate through all possible starting points $i$ and extend right pointer $j$.
• Space Complexity: $O(26) = O(1)$ to maintain the character frequency hash array.

3. Transition to Sliding Window ($O(N \cdot 26)$)

To optimize our time complexity to linear time, we utilize the Two-Pointer (Sliding Window) technique with a left pointer (L) and a right pointer (R), both starting at index 0.

Window Validity Rule

As we expand R to the right, we add characters to our frequency map and update max_f (the maximum frequency seen so far in the current window).

The window is valid if:

When this condition is violated, the window has more mismatches than our budget $k$ allows. We must shrink the window from the left by incrementing L.

4. Step-by-Step Sliding Window Execution

Let us trace the algorithm using the string s = "AABABBA" with $k = 1$.

Index:  0  1  2  3  4  5  6
Char:   A  A  B  A  B  B  A

1. Expand R to 0 (A): Frequency of A = 1. Max F = 1. Length = 1. Conversions = $1 - 1 = 0 \le 1$ (Valid). max_length = 1.
2. Expand R to 1 (A): Window: "AA". Max F = 2. Length = 2. Conversions = $2 - 2 = 0 \le 1$ (Valid). max_length = 2.
3. Expand R to 2 (B): Window: "AAB". Max F = 2 (A). Length = 3. Conversions = $3 - 2 = 1 \le 1$ (Valid). max_length = 3.
4. Expand R to 3 (A): Window: "AABA". Max F = 3 (A). Length = 4. Conversions = $4 - 3 = 1 \le 1$ (Valid). max_length = 4.
5. Expand R to 4 (B): Window: "AABAB". Max F = 3 (A). Length = 5. Conversions = $5 - 3 = 2 > 1$ (Invalid!).
   • Action: Shrink from left (L moves forward, removing characters and rescanning/adjusting frequencies until valid again).

5. First-Pass Sliding Window Pseudocode

def characterReplacement(s: str, k: int) -> int:
    l = 0
    max_length = 0
    max_f = 0
    hash_arr = [0] * 26
    
    for r in range(len(s)):
        hash_arr[ord(s[r]) - ord('A')] += 1
        max_f = max(max_f, hash_arr[ord(s[r]) - ord('A')])
        
        # If invalid, shrink from left
        while (r - l + 1) - max_f > k:
            hash_arr[ord(s[l]) - ord('A')] -= 1
            l += 1
            # Rescan hash array to find new max_f after contraction
            max_f = 0
            for i in range(26):
                max_f = max(max_f, hash_arr[i])
                
        # If valid, update max length
        if (r - l + 1) - max_f <= k:
            max_length = max(max_length, r - l + 1)
            
    return max_length

Bottleneck in First-Pass Optimal

In the code above, whenever we shrink L, we rescan the 26-size hash array to recompute max_f. This results in a time complexity of $O(N \cdot 26)$. Can we eliminate this 26-lookup scan?

6. The Ultimate Optimization: Eliminating Frequency Rescanning ($O(N)$)

Why Do We Not Need to Decrease max_f?

When our window becomes invalid and we shrink L, our max_f value might technically drop. However, we only care about finding a strictly longer substring than our current max_length.

• If max_length is currently 5, a future valid window must be of size 6 or greater.
• To achieve a window of size 6 with $k$ replacements, our max_f must be greater than or equal to its previous peak.
• Therefore, we never need to downgrade max_f when shrinking L. max_f only ever increases or stays the same throughout the entire execution.

Furthermore, we do not need a while loop that shrinks the window by multiple units. We can restrict our window size expansion: once we achieve a maximum valid window, we simply slide the window of that maximum size forward by incrementing both L and R together, ensuring our window never shrinks below our best historical length!

7. Final Optimal Solution

Here is the clean, production-grade $O(N)$ implementation without internal frequency scans or multi-step shrinkage loops.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        l = 0
        max_length = 0
        max_f = 0
        hash_arr = [0] * 26
        
        for r in range(len(s)):
            # 1. Include current character into frequency map
            char_idx = ord(s[r]) - ord('A')
            hash_arr[char_idx] += 1
            
            # 2. Track overall maximum frequency seen so far
            max_f = max(max_f, hash_arr[char_idx])
            
            # 3. Check if window is invalid. 
            # If invalid, shift left pointer forward by 1 (sliding the fixed-max window)
            if (r - l + 1) - max_f > k:
                hash_arr[ord(s[l]) - ord('A')] -= 1
                l += 1
                
            # 4. Record maximum valid window length
            max_length = max(max_length, r - l + 1)
            
        return max_length

Complexity Breakdown

Summary and Key Takeaways

• Problem Core: Find the longest substring requiring at most $k$ character replacements to make all characters identical.
• Conversion Formula: $\text{Conversions Needed} = \text{Window Length} - \text{Maximum Character Frequency}$.
• Greedy Strategy: Always preserve the most frequent character in the window and replace the minority characters.
• Why Two-Pointer/Sliding Window?: Substring and subarray problems with monotonic validity criteria are ideally solved using expanding/contracting window pointers.
• Key Optimization Insight: You never need to decrease max_f when shrinking the window. Since we only care about beating our historical max_length, max_f only needs to grow.
• Time Complexity Evolution:
  • Naive Brute-Force: $O(N^2)$
  • Intermediate Window with Hash Rescan: $O(N \cdot 26)$
  • Final Optimized Sliding Window: $O(N)$ with $O(1)$ space.