Lesson 13 — Sliding window II: validity with a budget

~25 minutes · Day 10 · sliding window · Python

Tonight's problem is Longest Repeating Character Replacement. Interviewers like it because the brute force is easy to imagine, but the efficient solution depends on one exact question: how do you know whether the current window can be repaired using at most k replacements?

The invariant

Same window, new validity rule: windowSize minus the most frequent char count must stay within k.

A sliding window is a changing slice s[left:right + 1]. Inside that slice, the most frequent character is the one you keep. Every other character is a character you would have to replace. So the number of replacements needed is:

windowSize - mostFrequentCharCount

If that number is at most k, the window is valid. If it is larger than k, shrink from the left until the budget works again.

The shaded span is the live window; the budget check decides whether left must move.

Character Replacement: the slow way first

The problem asks for the length of the longest substring that can be turned into one repeated character after changing at most k letters. The direct approach tries every starting point and keeps extending right:

def character_replacement_slow(s, k):
    best = 0
    for left in range(len(s)):
        count = {}
        for right in range(left, len(s)):
            ch = s[right]
            count[ch] = count.get(ch, 0) + 1
            size = right - left + 1
            if size - max(count.values()) <= k:
                best = max(best, size)
    return best

This works, but it is O(n^2): every left starts a fresh scan to the right. The better approach keeps one window alive and moves each pointer forward only as needed, which is the usual sliding-window shape of the two-pointer technique.

Character Replacement: the window way

Python's dict is enough for the character counts. The LeetCode statement uses uppercase English letters, so the count map has at most 26 live characters; checking max(count.values()) is a tiny constant-sized scan.

def character_replacement(s, k):
    count = {}                                  # char -> count inside window
    left = best = 0
    for right, ch in enumerate(s):
        count[ch] = count.get(ch, 0) + 1        # grow right
        size = right - left + 1
        while size - max(count.values()) > k:   # too many replacements
            count[s[left]] -= 1
            left += 1                          # shrink until valid
            size = right - left + 1
        best = max(best, size)
    return best

The loop is not trying to build the final answer in one jump. It keeps the current window honest: grow right, test the budget, shrink left only if the budget is broken, then record the best valid length seen so far.

Transfer: same budget, smaller alphabet

Max Consecutive Ones III: given a binary array, find the longest run of 1s if you may flip at most k zeroes.

Before opening the reveal: what is the validity rule? Say it out loud using the words window, zeroes, and k.

For the binary version, counting zeroes directly gives the whole validity rule.

def longest_ones(nums, k):
    left = zeroes = best = 0
    for right, x in enumerate(nums):
        if x == 0:
            zeroes += 1
        while zeroes > k:
            if nums[left] == 0:
                zeroes -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

What the trade buys you

The O(1) space is because the character set is fixed to uppercase English letters in this problem. If the alphabet were unbounded, the count map would grow with the number of distinct characters in the window.

Practice — answer before you scroll past

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

Your move (tonight)

Solve this on LeetCode, logging it in your Notion tracker with the cycle — predict → attempt → compare → encode:

1. Longest Repeating Character Replacement — first state the brute force and the budget rule, then code the window from memory.

For the encode step, write the invariant in your own words: the window is valid when the non-majority characters fit inside the replacement budget.