Longest Repeating Character Replacement — The Marquee Letters · DSA Quest

3Longest Repeating Character Replacement — The Marquee Letters

Boss 3: The Marquee Letters

Boss 2's window had a strict rule: one duplicate and it's broken.

This boss loosens the collar. The window is allowed to be imperfect, as long as fixing it costs no more than k swaps. Budgeted imperfection. Most mid-tier window problems look exactly like this.

The story

Your cinema's marquee currently reads:

"AABABBA"       k = 1

Seven letter tiles. You have one spare tile in your pocket. You want the longest contiguous stretch that can show a single repeated letter after at most one swap.

Look at ABBA (positions 3 to 6). It has three... wait, two Bs and two As. One swap can't fix that. But ABB (positions 3 to 5)? Two Bs, one A. Swap the A and you get BBB. Length 3 for one tile.

Can we do better? Take AABA (positions 0 to 3): three As, one B. One swap gives AAAA. Length 4. And nothing of length 5 works with a single tile, every 5-stretch of this marquee needs at least 2 swaps.

Answer: 4.

The mental move you just made, without noticing: in any stretch, you obviously keep the letter that appears most and swap out everyone else. The cost of a stretch is length - count_of_most_common_letter. Affordable means that cost is ≤ k.

The problem, dressed up properly

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

LeetCode 424. Uppercase English letters only, so 26 possible characters. Keep that in your back pocket.

The naive attempt

For every substring, count the letters, find the most common, check if length - max_count ≤ k.

def character_replacement(s, k):
    best = 0
    for i in range(len(s)):
        counts = {}
        for j in range(i, len(s)):
            counts[s[j]] = counts.get(s[j], 0) + 1
            if (j - i + 1) - max(counts.values()) <= k:
                best = max(best, j - i + 1)
    return best

O(n²) substrings, and each step scans up to 26 counts. Same disease as always: quadratic, with the same cure.

The weapon: a window that's broken by at most k

Slide a window and keep a count of every letter inside it. The window's health check:

window_length - max_frequency_inside ≤ k

If that holds, the window can be repainted into one letter within budget. If it breaks, shrink from the left.

One subtlety separates this boss from the last one, and it's worth slowing down for.

The max frequency is expensive to maintain honestly. When a letter enters the window, updating maxf is easy: maxf = max(maxf, count[new_letter]). But when a letter leaves during a shrink, recomputing the true max means scanning all 26 counts.

Here's the boss's secret weakness: you don't have to. Let maxf go stale. Keep the possibly-outdated value.

Why is that legal? Because maxf only ever being too large would be a problem, and stale maxf is only ever too large... which makes the health check too lenient, letting the window stay bigger than it deserves. And here's the trick: the answer is the biggest window we ever had, and a window only grows when a genuinely higher maxf is seen. A too-big window that's secretly unhealthy just coasts along without shrinking below its record size, and records are only set by honest windows. The stale value can never manufacture a longer answer than truth allows.

That argument feels slippery the first three times. The trace helps.

Watching it work

s = "AABABBA", k = 1

R   letter  counts after     maxf   len   len-maxf   action        best
0   A       A:1              1      1     0          ok            1
1   A       A:2              2      2     0          ok            2
2   B       A:2 B:1          2      3     1          ok (=k)       3
3   A       A:3 B:1          3      4     1          ok (=k)       4
4   B       A:3 B:2          3      5     2 > 1      shrink L=1    4
5   B       A:2 B:3          3      5     2 > 1      shrink L=2    4
6   A       A:2 B:3          3      5     2 > 1      shrink L=3    4

Best: 4, the AABA stretch, exactly as we eyeballed.

Two things to notice. After each over-budget step we shrink exactly once, not in a loop, so the window never gets smaller, it slides at its record size like a caterpillar. And from step 4 on, maxf = 3 is stale (the window at step 5 is ABABB, whose true max is 3, fine, but even when it drifts wrong later in other inputs, the record 4 already stands and can only be beaten honestly).

The code

def character_replacement(s: str, k: int) -> int:
    count = {}
    l = 0
    maxf = 0
    best = 0
    for r in range(len(s)):
        count[s[r]] = count.get(s[r], 0) + 1
        maxf = max(maxf, count[s[r]])
        if (r - l + 1) - maxf > k:      # over budget: slide, don't shrink-to-fit
            count[s[l]] -= 1
            l += 1
        best = max(best, r - l + 1)
    return best

Why `if` and not `while`?

Boss 2 needed while because the window had to become fully valid again. Here, one shrink after one grow keeps the window size constant, and since the answer only cares about the maximum size ever reached, a never-shrinking window is exactly what we want. A while that recomputed the true max and shrank to full health would also be correct, just more code and a 26x constant. Both pass interviews. Know why each works.

Gotchas

1. Recomputing max frequency on every shrink. Correct but wasteful, and worse, it signals you don't know the stale-maxf argument. If the interviewer asks "can maxf be outdated?", the answer is "yes, and it can't hurt the result, only delay shrinking a window that can no longer set a record."

2. Checking length - maxf < k instead of ≤ k. Cost exactly k is affordable, you have k tiles. Strict inequality silently throws away valid windows and fails on cases like "AB", k=1.

3. Trying to decide which letter to keep upfront. You don't pick the target letter, the window does, and it changes as the window moves. Running the whole algorithm 26 times, once per letter, works but is the long way around.

4. Window length after the slide. best = max(best, r - l + 1) must come after the possible shrink, or you'll record an over-budget window. In the code above the order is grow, fix, record. Keep it.

Complexity

R moves n times, L moves at most n times, counts update in O(1).

Time: O(n). Space: O(26) = O(1).

Boss down. XP gained.

The marquee reads AAAA BBA and from the highway nobody can tell the fourth A used to be a B.

What you walked away with:

Windows can tolerate budgeted imperfection: validity is length - maxf ≤ k, not perfection
The keep-the-majority insight: repaint cost is always length minus the most common letter's count
The stale-maxf trick, and the argument for why a lazy maximum can't inflate the answer
The caterpillar variant: slide-at-record-size instead of shrink-to-fit, when only the max window matters

Every window so far had a size the problem let you choose. The next boss fixes the size in advance and asks a sharper question: does some window of exactly this size match a fingerprint?

Next up: Boss 4 — The Spice Blend. A rival merchant claims your secret five-spice recipe is somewhere on his shelf, jars in a row, exact amounts, order scrambled. Slide a fixed-size window down the shelf and compare fingerprints without recounting from scratch. Permutations, meet windows.