Longest Repeating Character Replacement

Learning goal: Translate the replacement operation into a condition that can be checked for every substring.

Core idea A candidate window does not need to be constructed explicitly. If one character already appears maxFreq times, keep those occurrences and replace every other character. The number of required replacements is therefore the window length minus maxFreq.

A window is feasible when that replacement count is at most k. This turns an apparently combinatorial choice of target character into a simple frequency calculation.

Algorithm plan

• Examine contiguous windows of the string.
• Track the frequency of each uppercase character.
• Identify the largest frequency inside the current window.
• Keep the largest window whose replacement cost is at most k.

Micro-example For AABA, the length is 4 and A appears 3 times. The cost is 4 - 3 = 1, so it is valid when k = 1.

Pitfalls

• The target character is the most frequent character in the current window, not necessarily the globally most frequent character.
• A window can contain several different letters and still be valid.
• The answer is a length, not the substring itself.

Recap

• Keep the most frequent character unchanged.
• Replace all remaining characters.
• Validity is length - maxFreq <= k.

Learning goal: Understand why the quantity window length - max frequency measures the exact work needed.

Core idea Suppose a window contains counts for several letters. Choosing its most frequent letter as the final repeated character minimizes replacements: every occurrence of another letter must change, while every occurrence of the chosen letter can stay. Thus the window has a small amount of "slack" when most characters already agree.

The sliding window grows while its cost is affordable. Once the cost exceeds k, no larger window with the same left boundary can be valid, because adding characters cannot reduce the number of required changes enough to repair that boundary.

Algorithm plan

• Let left = 0 and scan right from left to right.
• Add s[right] to the frequency map.
• Update maxFreq using the newly added character.
• While right - left + 1 - maxFreq > k, remove s[left] and advance left.
• Record the widest valid window.

Micro-example For AABAB with k = 1, maxFreq = 3 and length 5, so the cost is 2. Shrinking removes the leftmost A, leaving a length-4 window with cost 1.

Pitfalls

• The inequality is <= k, not < k.
• Shrinking changes counts, but the current best answer should be updated only after the window is valid.
• maxFreq represents a count, not a character.

Recap

• Frequency concentration creates replacement slack.
• The left boundary moves only when the budget is exceeded.
• Each character enters and leaves the window at most once.

Learning goal: Assemble the validity test into a one-pass sliding-window algorithm.

Core idea The window is always repaired from the left after a new character is added. We maintain counts incrementally instead of recounting the substring. The value maxFreq is updated when the right boundary grows, which is enough to guide correct shrinking and preserve the linear-time bound.

Algorithm plan

counts = empty frequency map
left = 0
maxFreq = 0
best = 0

for right from 0 to n - 1:
    counts[s[right]] += 1
    maxFreq = max(maxFreq, counts[s[right]])

    while (right - left + 1) - maxFreq > k:
        counts[s[left]] -= 1
        left += 1

    best = max(best, right - left + 1)
return best

Micro-example At right = 3 in AABABBA, the window is AABA: length 4, maxFreq = 3, and cost 1. It contributes 4 to best.

Pitfalls

• Do not reset maxFreq while shrinking.
• Do not shrink before adding the new right character.
• The while condition must use the current window length.

Recap

• Add on the right, remove on the left.
• Repair only when replacement cost exceeds k.
• Record the maximum valid length.

Learning goal: Trace every pointer movement and see how the widest valid window emerges.

Core idea We use s = AABABBA and k = 1. As right expands the window, maxFreq records the largest frequency seen while growing. When the estimated replacement cost becomes too large, we remove characters from the left until the window passes the validity test again.

The important detail is that after shrinking, maxFreq can be slightly stale. For example, a window may truly have a maximum count of 2 while the stored value remains 3. That does not cause an incorrect answer: the stale value can only make the current window look easier to repair, and it never creates a new best length unless that length was achievable during an earlier valid expansion.

Algorithm plan

• Expand through each character from left to right.
• Update the count and possibly maxFreq.
• Shrink once or repeatedly while the estimated cost is greater than 1.
• Record the valid width after repair.

Micro-example The first length-5 window is AABAB. Its stored maxFreq is 3, so its cost is 2; remove the first A to obtain ABAB, whose cost is 1.

Pitfalls

• A shrink event is not a failure; it is how the window restores its invariant.
• Do not expect maxFreq to decrease immediately after removing a character.
• Compare widths after shrinking, not before.

Recap

• The best width reaches 4 at AABA.
• Later windows remain valid only after left-side repair.
• The final answer is 4.

Learning goal: Distinguish the safe stale-maximum optimization from mistakes that break the sliding-window invariant.

Core idea When the left pointer removes a character, the true maximum frequency inside the window might decrease. Recomputing that maximum on every shrink is unnecessary. Keep maxFreq as the largest frequency observed during expansion; if it is stale, it may make the estimated cost look smaller, but it cannot cause the algorithm to miss a larger valid answer.

The reason is that a stale maximum never increases the recorded width beyond a width that was already supported during an earlier expansion. The window only needs to grow past its previous best when the newly added character raises a real frequency maximum.

Algorithm plan

• Update maxFreq only after adding s[right].
• Shrink while the estimated cost is greater than k.
• Never scan all 26 counts inside the shrink loop.
• Test k = 0, a uniform string, and a string with all distinct letters.

Micro-example After shrinking AABAB to ABAB, the true maximum is 2, but stored maxFreq may remain 3. The estimate says cost 1, which is safe for deciding that width 4 does not need further shrinking.

Pitfalls

• Recomputing the true maximum on every shrink can turn the method into O(26n); with a fixed alphabet it is still bounded, but the intended invariant is simpler and fully one-pass.
• Shrinking only once can leave an invalid window when the budget is much smaller.
• Forgetting to decrement the removed character produces incorrect counts.

Recap

• A stale maxFreq is intentional, not a bug.
• Use a while loop for repair.
• Edge cases naturally follow from the same inequality.

Learning goal: Justify the O(n) time and O(1) space bounds and recognize the reusable pattern.

Core idea Although the algorithm contains a while loop inside a for loop, the total work is linear. The right pointer crosses each position once, and the left pointer also crosses each position at most once. With only 26 uppercase English letters, the frequency table has constant size.

This pattern applies whenever a contiguous window can be characterized by a budget: grow to explore possibilities, then shrink only when the budget is violated. The crucial design step is finding a quantity that measures the minimum repair cost—in this problem, length - maxFreq.

Algorithm plan

• Maintain counts for the current window.
• Maintain the largest observed single-character count.
• Enforce window length - maxFreq <= k.
• Track the maximum repaired width.

Micro-example For AABABBA, seven characters are added and at most seven characters are removed. The frequency array has 26 entries, so the final complexity is O(n) time and O(1) auxiliary space.

Pitfalls

• Nested loops do not automatically imply quadratic time; analyze pointer movement.
• Space is constant here because the alphabet is fixed, not because the input is small.
• Returning the final window's width instead of the maximum width can lose an earlier answer.

Recap

• Time: O(n).
• Space: O(1) for uppercase English letters.
• The reusable invariant is a bounded repair cost inside a moving window.