Longest Repeating Character Replacement

1. Problem & Core Objective

The problem

You are given a string s and an integer k. You may choose any character of the string and change it to any other uppercase English character, and you may do this at most k times.

Return the length of the longest substring containing the same letter you can obtain.

Input:  s = "ABAB",    k = 2      Output: 4      (change both A's to B, or both B's to A)
Input:  s = "AABABBA", k = 1      Output: 4      ("AABA" → change the B → "AAAA")

Constraints:

• 1 <= s.length <= 10^5
• s consists of only uppercase English letters
• 0 <= k <= s.length

What the interviewer is actually testing

The template is the same longest-valid window as the previous question. The difficulty is entirely in deriving the validity condition — the problem doesn't hand it to you.

1. Can you derive windowLength − maxFreq <= k? That expression is the whole problem. Everything else is boilerplate.
2. Do you realize you never simulate the replacements? You only count how many would be needed.
3. Can you defend the stale maxFreq? The efficient version never decreases maxFreq when shrinking, which looks like a bug and isn't. Interviewers who know this question probe it specifically.
4. Do you see why the window is monotonic? Growing can only increase the replacements needed, which is what licenses the shrink loop.

2. First-Principles Thought Process

Step 1 — Constraints

n up to 10^5, so O(n) or O(26n) is expected and O(n²) is not.

The alphabet is uppercase English only — 26 characters. That's the signal to use int[26] rather than a HashMap (06 — Arrays & Hashing).

Step 2 — Restate the goal in terms of a window

We're looking for a contiguous substring that can be made uniform with at most k changes. So:

Find the longest window that can be made all-one-character using at most k replacements.

Contiguous + longest + a budget constraint → longest-valid sliding window.

Step 3 — Derive the validity condition

This is the step that matters. For a given window, what's the cheapest way to make it uniform?

Keep whichever character already appears most often, and replace everything else. Any other choice replaces more characters.

So for a window of length L where the most frequent character appears maxFreq times:

replacements needed = L − maxFreq

And the window is valid exactly when:

windowLength − maxFreq <= k

Worked example. Window "AABAB", so L = 5. Counts: A appears 3 times, B twice, so maxFreq = 3. Replacements needed = 5 − 3 = 2. Valid if k >= 2.

Why you never simulate the replacements: you only need to know how many would be required, not which ones. The string is never modified.

Step 4 — Confirm monotonicity

Windowing is only sound if growing the window can't make an invalid window valid again.

Adding one character increases L by 1. It increases maxFreq by at most 1 — and only if the added character happens to be the current majority. So L − maxFreq either stays the same or increases. It never decreases.

That's the monotonicity that licenses shrinking from the left: once invalid, a window stays invalid until you shrink it.

Step 5 — Maintaining maxFreq

The obvious approach recomputes maxFreq by scanning all 26 counts after each change: O(26) per step, so O(26n) overall — which is O(n) with a constant of 26.

The refinement is to keep maxFreq as a running value and never decrease it when shrinking. That looks wrong, and defending it is the question's real test — see the counter-questions on Approach 3.

3. Solution Paths

Approach 1 — Brute force: every substring

public int characterReplacement(String s, int k) {
    int best = 0;
    for (int i = 0; i < s.length(); i++) {
        int[] count = new int[26];
        int maxFreq = 0;
        for (int j = i; j < s.length(); j++) {
            count[s.charAt(j) - 'A']++;
            maxFreq = Math.max(maxFreq, count[s.charAt(j) - 'A']);

            int len = j - i + 1;
            if (len - maxFreq <= k) best = Math.max(best, len);
        }
    }
    return best;
}

Extends every start rightward, tracking counts incrementally within each start.

• Time: O(n²).
• Space: O(1) — 26 ints.

Counter-questions on this approach

⭐ "When a window becomes invalid, why do you keep extending it?"

I shouldn't, and that's a real inefficiency even within the brute force — once len - maxFreq > k for this start, extending further only makes it worse, since the expression is monotonic. I could break. But the deeper waste is restarting from i + 1 at all: most of the failing window is still usable if I shrink from the left instead of discarding it.

"Is maxFreq correct here, given you never reset it within a start?"

Yes, because within a single start the window only ever grows — counts never decrease, so the running maximum is genuinely the maximum. The subtlety only appears once shrinking enters the picture, in Approach 3.

Approach 2 — Sliding window, recomputing maxFreq

public int characterReplacement(String s, int k) {
    int[] count = new int[26];
    int left = 0, best = 0;

    for (int right = 0; right < s.length(); right++) {
        count[s.charAt(right) - 'A']++;

        while (right - left + 1 - maxCount(count) > k) {    // recompute each time
            count[s.charAt(left) - 'A']--;
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

private int maxCount(int[] count) {
    int m = 0;
    for (int c : count) m = Math.max(m, c);
    return m;
}

Trace on s = "AABABBA", k = 1:

Answer: 4 ✓ (the substring "AABA", changing the B)

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

Counter-questions on this approach

⭐ "You scan 26 counts on every shrink check. Is that really O(n)?"

Yes — 26 is a constant fixed by the problem's alphabet, not a function of n. So it's O(26n) which is O(n). It's a genuine constant factor though, and it can be removed entirely, which is the next approach.

⭐ "Why is right - left + 1 - maxFreq the right thing to compare against k?"

right - left + 1 is the window length. maxFreq is how many characters I can keep — the majority character. Everything else must be replaced, so the replacements needed are the difference. The window is valid exactly while that's within budget.

"How do you know shrinking will ever restore validity?"

Because the expression is monotonic in window size: removing a character reduces L by 1 and reduces maxFreq by at most 1, so L − maxFreq never increases when shrinking. In the worst case the window shrinks to length 1, where the value is 0 and any k >= 0 is satisfied. The loop always terminates.

Approach 3 — Sliding window with a running maxFreq (optimal)

public int characterReplacement(String s, int k) {
    int[] count = new int[26];
    int left = 0, maxFreq = 0, best = 0;

    for (int right = 0; right < s.length(); right++) {
        count[s.charAt(right) - 'A']++;
        maxFreq = Math.max(maxFreq, count[s.charAt(right) - 'A']);

        while (right - left + 1 - maxFreq > k) {
            count[s.charAt(left) - 'A']--;      // note: maxFreq is NOT decreased
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

The only change from Approach 2: maxFreq is updated incrementally and never decreased when shrinking.

• Time: O(n) — no inner 26-scan at all.
• Space: O(1).

Counter-questions on this approach

⭐ "You never decrease maxFreq when you shrink. Isn't it now wrong — a stale, too-large value?"

It can be stale, yes — and the answer is still correct. Here's why.

A too-large maxFreq makes the condition L − maxFreq > k harder to trigger, so the window shrinks less than it strictly should. That means the window can temporarily hold a length that isn't genuinely achievable.

But best is only updated with right - left + 1, and the window never grows beyond one character per iteration. For best to increase, the window must reach a length it has never reached before — and reaching a new maximum length requires a genuinely valid window with an up-to-date maxFreq, because maxFreq is refreshed every time a character enters. So a stale value can delay shrinking, but it can never manufacture a new maximum.

The invariant is: best never exceeds the largest genuinely valid window seen.

⭐ "So would recomputing maxFreq on every shrink also be correct?"

Yes, and that's Approach 2 — correct and easier to defend, at O(26n). I'd write that version first if I weren't confident in the staleness argument. The optimal version is only worth claiming if you can justify it, because "it passes the tests" is not an answer to this follow-up.

"Does the window ever actually shrink here, or does left just track right?"

It shrinks by at most one position per iteration, because the condition is checked after adding exactly one character. In practice the while behaves like an if — worth noting, though writing it as a while keeps it consistent with the general template and costs nothing.

"Why s.charAt(right) - 'A' rather than - 'a'?"

The constraints say uppercase English letters, and 'A' is the base of that range. Using 'a' would produce large negative indices and throw. It's a one-character difference from the previous question, and exactly the kind of thing to check against the constraints rather than habit.

Comparison

4. Why the Optimal Wins

Against brute force. Same restart-versus-shrink argument as the previous question: when a window becomes invalid, the brute force abandons it and rebuilds from the next index, while the window removes just enough from the left and continues. O(n²) → O(n).

Against the recomputing version. Both are O(n) asymptotically, since 26 is a constant. The running version removes that factor of 26 entirely. It's a constant-factor improvement bought with a subtle correctness argument — which is exactly the trade to discuss rather than assume.

Be honest about this one:

"Both versions are O(n). The running-maxFreq version is faster by a constant factor, but it relies on a staleness argument that's easy to get wrong. If I weren't confident in that argument I'd ship the recomputing version — a correct O(26n) beats a subtly-wrong O(n)."

Why O(n) is the floor. Every character must be examined, since the optimal window could begin or end anywhere. So O(n) is optimal.

The transferable lesson is the derivation, not the code:

When a problem gives you a budget ("at most k changes"), the window's validity condition is usually "cost of this window ≤ budget" — and your job is to find a cheap way to compute that cost incrementally.

Here the cost was L − maxFreq. In Minimum Window Substring it's a have/need counter. Same shape.

5. Java Prerequisites

Fixed-alphabet counting

int[] count = new int[26];
count[s.charAt(i) - 'A']++;      // UPPERCASE — base is 'A', not 'a'

'A' is 65 and 'Z' is 90, so c - 'A' maps to 0–25. Using 'a' (97) as the base on uppercase input gives negative indices and throws ArrayIndexOutOfBoundsException.

This is O(1) space, not O(k) — 26 is fixed by the problem, not a function of the input. See 03.

Running maximum

maxFreq = Math.max(maxFreq, count[idx]);

Only the count that just changed can raise the maximum, so there's no need to rescan — that's what makes the O(26) factor removable.

Window length

right - left + 1

Inclusive both ends. Check on one character: 0 - 0 + 1 = 1.

while vs if in the shrink step

while (right - left + 1 - maxFreq > k) { ... }

Because exactly one character enters per iteration, the window becomes invalid by at most one, so this behaves as an if. Writing while costs nothing and keeps the code consistent with the general template — which matters when you adapt it to a problem where multiple shrinks are needed.

Operator precedence

right - left + 1 - maxFreq > k

All the arithmetic binds tighter than >, so this parses as (right - left + 1 - maxFreq) > k. Correct, but adding the parentheses makes the intent obvious to a reader.

6. Interview Communication Guide

Clarifying questions

1. "Is the string uppercase only?" — yes, which is what makes int[26] valid. Get this before writing - 'A'.
2. "Can I replace a character with any letter, or only ones already present?" — any uppercase letter. It doesn't change the algorithm, but it confirms the L − maxFreq reasoning.
3. "Does the substring have to be contiguous?" — yes. A subsequence version would be a different problem.
4. "Can k be 0, or larger than the string?" — both are allowed by the constraints. k = 0 means "longest run of identical characters"; k >= n means the whole string.
5. "Do I return the length or the substring?" — the length.

The pitch

"I want the longest contiguous window I can make uniform with at most k changes.

The key question is: for a given window, how many changes does it need? The cheapest strategy is to keep whichever character already appears most often and replace the rest. So the cost is windowLength − maxFrequency, and the window is valid while that's at most k.

That condition is monotonic — adding a character increases the length by 1 and the max frequency by at most 1, so the cost never decreases as the window grows. That's what makes a sliding window sound.

So: expand right always, and while the cost exceeds k, shrink from the left. Record the length after validity is restored. Since the alphabet is 26 uppercase letters, I'll count with an int[26].

The simple version rescans the 26 counts to find maxFreq on each check — that's O(26n), which is O(n). I can drop the 26 by tracking maxFreq incrementally and never decreasing it when shrinking. That looks wrong, but it's safe: a stale maxFreq only delays shrinking, and best can only improve when the window reaches a genuinely new maximum length, which requires a fresh maxFreq."

Edge cases to raise proactively

k = 0 is the case to volunteer — it reduces to "longest run of a single repeated character", and it's a good check that the cost formula degenerates correctly. k >= n is the other: the answer is the whole string, since everything can be replaced.

7. Follow-Up Questions — Modified Constraints

The interviewer changes a constraint of the original problem and asks you to solve it again. ⭐ marks the most likely.

⭐ "What if the string weren't restricted to uppercase — full Unicode?"

int[26] breaks. Switch to a HashMap<Character,Integer> for the counts. maxFreq can still be tracked incrementally the same way, so the algorithm is unchanged — only the container. Space becomes O(k) in the distinct characters present rather than O(1).

"What if you had to return the substring itself rather than its length?"

Record left alongside best whenever the length improves, then substring(bestLeft, bestLeft + best). No complexity change.

"What if you could only replace characters with one specific target letter, chosen in advance?"

Much simpler. The cost of a window becomes windowLength − count[target], with no maximum to track. Run the same window once and you're done — O(n). If the target isn't given, run it 26 times, once per candidate letter, and take the best: O(26n), still O(n). That's also a clean way to sidestep the staleness argument entirely, which is worth offering if the interviewer pushes on it.

"What if the replacements had different costs per character?"

The "keep the majority character" reasoning breaks — the cheapest character to standardize on is no longer necessarily the most frequent one. You'd need, for each window, the minimum total cost over all 26 target letters, which is O(26) per window and pushes you back toward the recomputing version.

"What if k could change between queries on the same string?"

Each query is an independent O(n) run, so q queries cost O(qn). To do better you'd note that the answer is monotonic in k — a larger budget never gives a shorter answer — so you could precompute answers for all k from 0 to n in O(n²) and then answer each query in O(1). Worth it only if q is large.

"What about the longest substring with at most k distinct characters?" (LC 340)

A different invariant on the same template: track counts in a map and shrink while map.size() > k. O(n) time, O(k) space. Same shape, and a good demonstration that the template transfers once you can state the validity condition.