Longest Repeating Character Replacement

1. Step 1: Initialize Solution.characterReplacement

   Replace the empty starter with the first real state owned by Solution.characterReplacement. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.

2. Step 2: Pass the Alternating case

   Complete the readable core algorithm for one representative Interview case. Maintain a window whose length minus its highest character frequency is at most k.

3. Step 3: Harden the Shrink Required boundary

   Repair the reviewed boundary and pass the complete submission contract. A window needs exactly length minus its most frequent character count replacements. The algorithm removes left characters whenever this lower bound exceeds k and records the largest retained length. A stale maximum can delay shrinking but cannot create a new larger answer unless a window of that length was previously feasible.

• The stored maximum frequency may be stale after the left edge moves; that is safe for finding the maximum length but should not be recomputed by scanning the map every iteration.
• arrays strings two pointers sliding window
• hashing and sets

• LeetCode 424 — Longest Repeating Character Replacement

• Shrink Until the Window Is Valid(opens in a new tab)

  Shrink Until the Window Is Valid isolates after shrinking, the current half-open window is valid and no earlier left boundary works for the same right endpoint. That focused state discipline is required when implementing longest repeating character replacement as a complete Interview Problem.

Expand a right edge while counting characters and tracking the largest count seen in a window; shrink from the left whenever window length minus that count exceeds k.

Why it works: A window needs exactly length minus its most frequent character count replacements. The algorithm removes left characters whenever this lower bound exceeds k and records the largest retained length. A stale maximum can delay shrinking but cannot create a new larger answer unless a window of that length was previously feasible.

class Solution:
    def characterReplacement(self, s, k):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        counts = {}
        left = 0
        max_frequency = 0
        best = 0
        for right, character in enumerate(s):
            counts[character] = counts.get(character, 0) + 1
            max_frequency = max(max_frequency, counts[character])
            while right - left + 1 - max_frequency > k:
                counts[s[left]] -= 1
                left += 1
            best = max(best, right - left + 1)
        return best

• Longest Unique-Character Window(opens in a new tab)