Loading…

mediumStringsLC #424Frequently asked

Longest Repeating Character Replacement

Q: How do you solve Longest Repeating Character Replacement using the Brute Force — Test Every Substring approach?

When to use it: Say it first to anchor the baseline and to surface the 'replacements = length − maxFreq' formula. For each start index `i`, extend `j` to the right while maintaining a frequency table of the window `[i..j]`. The cost to make that window uniform is `(j − i + 1) − maxFreqInWindow`. If that cost is ≤ k, the window is feasible; record its length. Restart from the next start. **Why this is the natural first attempt.** It encodes the definition directly and, crucially, forces you to articulate the central fact: the cheapest way to unify a window is to keep its most common letter and replace the rest, so the replacement cost is `length − maxFreq`. That formula is the heart of the optimal solution too. **Why we don't ship this.** Restarting at every start index re-counts overlapping windows. With `n` up to `10⁵`, that's too slow. The waste is the same as in other window problems — when a window starting at `i` becomes infeasible, almost all of the counting for `i+1` overlaps it. A single sliding window reuses that work. Time complexity: O(n²). Space complexity: O(1).

LCPractice

Sliding Window · 3 of 6 · 10 min

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.

In plain English

We want the longest contiguous window that can be turned into a single repeated letter using at most k replacements. Within a window, the cheapest way is to keep its most frequent letter and replace everything else — so the cost is windowLength minus the count of that majority letter.

Examples

Example 1

Input: s = "ABAB", k = 2
Output: 4
Note: Replace the two A's (or two B's) to make "BBBB" (or "AAAA"); the whole string of length 4 works.

Example 2

Input: s = "AABABBA", k = 1
Output: 4
Note: Window "AABA" → replace the one B to get "AAAA" (length 4). Or "ABBA" → one replacement.

Example 3

Input: s = "AAAA", k = 0
Output: 4
Note: Already uniform; no replacements needed.

Constraints

1 ≤ s.length ≤ 10⁵
s consists of only uppercase English letters
0 ≤ k ≤ s.length

Clarifying questions4First question: What can I change a character to?Explore questions

Q1.What can I change a character to?
Any uppercase letter. So the target letter for a window is whichever already appears most often there.
Q2.Is k a hard cap or exactly k?
At most k — using fewer (or zero) replacements is allowed.
Q3.Substring or subsequence?
Substring — contiguous. That's why a sliding window fits.
Q4.What's the alphabet size?
26 uppercase letters, so the frequency table is constant size and the space is O(1).

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Find the longest window you can make all-equal by replacing at most k characters. A window is feasible when (windowLength − countOfMostFrequentChar) ≤ k — that difference is the number of replacements needed. Slide a window: expand right, and when it becomes infeasible, shift left by one. Track the answer as the max window size. O(n) time, O(1) space (26 counts).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you derive the validity condition windowLen − maxFreq ≤ k and run an O(n) sliding window, and whether you understand why maxFreq need not be decremented on shrink.

Where candidates slip

Recomputing maxFreq by scanning the whole count array every step (making it O(26n) or worse), or shrinking the window in a while loop that mishandles maxFreq.

How to stand out

State the brute force, derive replacements = windowLen − maxFreq, then explain the subtle point: a stale maxFreq can only keep the window from growing, never produce an invalid-but-larger answer, so we never need to recompute it downward.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Test Every Substring	`O(n²)`	`O(1)`	Say it first to anchor the baseline and to surface the 'replacements = length − maxFreq' formula.	Read
2	Sliding Window + Frequency Table (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Phrase it as 'one window, valid while windowLen − maxFreq ≤ k, shift left when it isn't'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewLongest uniform window after ≤ k replacementsCan validity be a simple count test?No (recheck all)Yes (len − maxFreq ≤ k)Explore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Test Every Substring

TimeO(n²)SpaceO(1)

Say it first to anchor the baseline and to surface the 'replacements = length − maxFreq' formula.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The answer is some substring. Given a substring, how many replacements does it take to make it uniform?

2Hint 2Explore hint

Count each letter's frequency in the substring; the cheapest unification keeps the most frequent letter, so cost = length − maxFreq.

3Hint 3Explore hint

For each start i and end j, compute that cost; if ≤ k, the substring is feasible. Track the longest feasible one.

A · Core idea

For each start index i, extend j to the right while maintaining a frequency table of the window [i..j]. The cost to make that window uniform is (j − i + 1) − maxFreqInWindow. If that cost is ≤ k, the window is feasible; record its length. Restart from the next start.

Why this is the natural first attempt. It encodes the definition directly and, crucially, forces you to articulate the central fact: the cheapest way to unify a window is to keep its most common letter and replace the rest, so the replacement cost is length − maxFreq. That formula is the heart of the optimal solution too.

Why we don't ship this. Restarting at every start index re-counts overlapping windows. With n up to 10⁵, that's too slow. The waste is the same as in other window problems — when a window starting at i becomes infeasible, almost all of the counting for i+1 overlaps it. A single sliding window reuses that work.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "AABA", k = 1

i=0

"AABA": maxFreq(A)=3, cost 4−3=1 ≤ 1

Statefeasible, len 4

Final result4

C · Code with teaching comments

Reference implementation previewpublic int characterReplacement(String s, int k) { int n = s.length(); int best = 0; for (int i = 0; i < n; i++) { int[] count = new int[26];Explore the full code

solution.javaJava

Brute Force — Test Every Substring — reference

3 teaching notes

1
public int characterReplacement(String s, int k) {
2
    int n = s.length();
3
    int best = 0;
4
    for (int i = 0; i < n; i++) {
5
        // Fresh frequency table per start — the wasteful restart.
6
        int[] count = new int[26];
7
        int maxFreq = 0;
8
        for (int j = i; j < n; j++) {
9
            count[s.charAt(j) - 'A']++;
10
            // Most frequent letter so far in this window.
11
            maxFreq = Math.max(maxFreq, count[s.charAt(j) - 'A']);
12
            int windowLen = j - i + 1;
13
            // Replacements needed = windowLen − maxFreq; feasible when ≤ k.
14
            if (windowLen - maxFreq <= k) {
15
                best = Math.max(best, windowLen);
16
            }
17
        }
18
    }
19
    return best;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

The brute force pays off by surfacing the key invariant: replacements needed = windowLength − maxFreq. Once you have that, the only remaining inefficiency is restarting the count at each start — exactly what a sliding window eliminates.

ComplexityO(n²) time, O(1) space — There are O(n²) substrings; maintaining counts incrementally as j extends makes each O(1), so O(n²) time. A fixed 26-slot count array → O(1) space.

E · Edge cases and pitfalls3Recreating the count array per start — the quadratic cost.Explore edge cases

Pitfalls

Recreating the count array per start — the quadratic cost.
Computing cost as length − k instead of length − maxFreq.
Indexing past 26 if the input isn't strictly uppercase letters.

03.2

Approach 2 of 2 · Optimal

Sliding Window + Frequency Table (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Phrase it as 'one window, valid while windowLen − maxFreq ≤ k, shift left when it isn't'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Keep one window and a count of letters in it. The window is valid while (length − maxFreq) ≤ k.

2Hint 2Explore hint

Expand right by adding s[right] and updating maxFreq. If the window becomes invalid, move left forward by one (decrementing that letter's count).

3Hint 3Explore hint

Subtle point: you never need to lower maxFreq when shrinking. A too-high maxFreq only makes the window look valid; but the window can't grow past the best it already achieved, so the answer stays correct.

A · Core idea

Maintain a window [left, right] and a 26-slot frequency table. Extend right one character at a time, incrementing its count and refreshing maxFreq. After each expansion, if the window is invalid — (right − left + 1) − maxFreq > k — slide left forward by one, decrementing the departing character. Record the window length as a candidate answer.

Why the validity test is `windowLen − maxFreq ≤ k`. To make the whole window one letter, keep the letter that already appears most (maxFreq of them) and replace every other character. The number of replacements is therefore windowLen − maxFreq. The window is achievable iff that's within budget k.

Why a single `if`, not a `while`, suffices. We're after the longest valid window. Once the window reaches some maximum valid length, any later expansion that breaks validity only needs the window to shift, not shrink — keeping its size constant while sliding rightward. If the new region is better it'll grow again; if not, the window glides at its current width. So shifting left by exactly one per invalid expansion is enough, and the window length is monotonically non-decreasing.

The subtle bit: why we don't decrement `maxFreq` on shrink. When left advances, the true most-frequent count might drop, so maxFreq can become stale (too high). That's fine. A stale, too-high maxFreq makes windowLen − maxFreq smaller, i.e. the window looks more valid. But because the window length never decreases, a falsely-valid window of the same size can't produce an answer larger than one we already legitimately achieved — it just lets the window slide. The recorded best is only ever updated to a length we genuinely reached when maxFreq was accurate. So skipping the (expensive) recomputation of maxFreq is safe and keeps the pass O(n).

Why O(n) time and O(1) space. Each pointer sweeps the string once; the frequency table is constant size.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "AABABBA", k = 1

Array state

right=3

"AABA" maxFreq(A)=3, cost 1 ≤ 1, len 4

left ↓

[0]

[1]

[2]

right ↓

[3]

[4]

[5]

[6]

Current pointerResolved stateNot processed

Final result4

C · Code with teaching comments

solution.javaJava

Sliding Window + Frequency Table (Optimal) — optimal

4 teaching notes

1
public int characterReplacement(String s, int k) {
2
    int[] count = new int[26];
3
    int left = 0, maxFreq = 0, best = 0;
4
    for (int right = 0; right < s.length(); right++) {
5
        int idx = s.charAt(right) - 'A';
6
        count[idx]++;
7
        // Most frequent letter count; may stay stale after a shrink — intentionally.
8
        maxFreq = Math.max(maxFreq, count[idx]);
9
        // Replacements needed exceed budget → window invalid.
10
        if ((right - left + 1) - maxFreq > k) {
11
            count[s.charAt(left) - 'A']--;
12
            left++;
13
        }
14
        // Window length is the answer candidate, never maxFreq.
15
        best = Math.max(best, right - left + 1);
16
    }
17
    return best;
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

Two ideas combine: 'cost to unify = length − maxFreq' gives the validity test, and 'the longest window never needs to shrink, only slide' lets a stale maxFreq stay uncorrected. Recognizing that a never-shrinking window tolerates an over-estimated statistic is the non-obvious move that keeps this linear.

ComplexityO(n) time, O(1) space — Both `left` and `right` move forward only, each at most n times → O(n) total. The frequency table is a fixed 26 ints → O(1) space.

E · Edge cases and pitfalls6s = "AAAA", k = 0 — Always uniform; cost 0 every step, window grows to full length 4.Explore edge cases

Edge cases handled

s = "AAAA", k = 0Always uniform; cost 0 every step, window grows to full length 4.
s = "ABCDE", k = 0Every 2-length window costs 1 > 0, so the window stays length 1 → answer 1.
s = "AAAB", k = 0Window "AAA" is valid (cost 0); adding B costs 1 > 0 so it slides → answer 3.

Pitfalls

Recomputing maxFreq by scanning all 26 counts on every shrink — works but unnecessary; the stale value is safe.
Returning maxFreq or maxFreq + k instead of the window length.
Using a while loop to shrink and then mismanaging maxFreq, producing a wrong (too-short) window.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic 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++) { int idx = s.charAt(right) - 'A';Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong validity formula

The replacements needed to unify a window is its length minus the most frequent letter's count — not its length minus k.

Explore the code comparison

Don't write this

if (right - left + 1) - k > max_freq:
    ...

Write this instead

if (right - left + 1) - max_freq > k:
    count[ord(s[left]) - ord('A')] -= 1
    left += 1

Returning maxFreq instead of window length

The answer is the size of the longest achievable uniform window, which is right − left + 1, not the frequency of the dominant letter.

Explore the code comparison

Don't write this

best = Math.max(best, maxFreq);

Write this instead

best = Math.max(best, right - left + 1);

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sliding window; valid when windowLen − maxFreq ≤ k

Code pattern to memorize

count = [0]*26
left = 0
maxFreq = 0
best = 0
for right, c in enumerate(s):
    count[c] += 1
    maxFreq = max(maxFreq, count[c])
    while (right - left + 1) - maxFreq > k:
        count[s[left]] -= 1
        left += 1
    best = max(best, right - left + 1)
return best

Rules to remember

1Replacements needed = windowLength − maxFreq (keep the majority char, replace the rest).
2Window is valid iff that count ≤ k.
3Use an if (shift left by one) — the window never needs to shrink more than one step per expansion.
4You don't need to decrease maxFreq when shrinking; a stale-but-too-high maxFreq never produces a wrong larger answer.
5Answer is the largest valid window length seen — the window length itself, not maxFreq.

Use this pattern when

Longest window that becomes uniform/valid after at most k edits
Validity depends on the window length minus a frequency statistic
You can keep a frequency table and a running max frequency
A 'replace up to k' or 'flip up to k' contiguous-window question

Choose another pattern when

Replacements unlimited → answer is just the whole string length
Need zero repeats instead of all-same → Longest Substring Without Repeating
Counting subsequences, not contiguous windows → DP

Interview takeaway

The trick is the validity test `windowLen − maxFreq ≤ k`: the cost to unify a window is its size minus its most common character. Combined with a never-shrink-more-than-one window, that gives a clean O(n) pass — a template for 'longest window fixable in k edits' problems.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternSliding window with a frequency statistic and a never-shrink-more-than-one invariant. Reach for it on 'longest window fixable in k edits' problems. Same family as Max Consecutive Ones III and At Most K Distinct.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Longest Substring Without Repeating Characters
Variable window again, but validity is 'no repeats' via a last-index map.
Max Consecutive Ones III
Coming soon
Flip at most k zeros — window valid while zeros-in-window ≤ k; the binary special case.
Longest Substring with At Most K Distinct Characters
Coming soon
Window valid while the count map has at most k keys.
Minimum Window Substring
The shrinking-window cousin: grow to satisfy a need, then minimize.

Same pattern

←

Longest Substring Without Repeating Characters

Continue · Next problem

Minimum Window Substring

mediumStringsLC #424Frequently asked

Longest Repeating Character Replacement

LCPractice

Sliding Window · 3 of 6 · 10 min

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.

In plain English

Examples

Example 1

Input: s = "ABAB", k = 2
Output: 4
Note: Replace the two A's (or two B's) to make "BBBB" (or "AAAA"); the whole string of length 4 works.

Example 2

Input: s = "AABABBA", k = 1
Output: 4
Note: Window "AABA" → replace the one B to get "AAAA" (length 4). Or "ABBA" → one replacement.

Example 3

Input: s = "AAAA", k = 0
Output: 4
Note: Already uniform; no replacements needed.

Constraints

1 ≤ s.length ≤ 10⁵
s consists of only uppercase English letters
0 ≤ k ≤ s.length

Clarifying questions4First question: What can I change a character to?Explore questions

Q1.What can I change a character to?
Any uppercase letter. So the target letter for a window is whichever already appears most often there.
Q2.Is k a hard cap or exactly k?
At most k — using fewer (or zero) replacements is allowed.
Q3.Substring or subsequence?
Substring — contiguous. That's why a sliding window fits.
Q4.What's the alphabet size?
26 uppercase letters, so the frequency table is constant size and the space is O(1).

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you derive the validity condition windowLen − maxFreq ≤ k and run an O(n) sliding window, and whether you understand why maxFreq need not be decremented on shrink.

Where candidates slip

Recomputing maxFreq by scanning the whole count array every step (making it O(26n) or worse), or shrinking the window in a while loop that mishandles maxFreq.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Test Every Substring	`O(n²)`	`O(1)`	Say it first to anchor the baseline and to surface the 'replacements = length − maxFreq' formula.	Read
2	Sliding Window + Frequency Table (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Phrase it as 'one window, valid while windowLen − maxFreq ≤ k, shift left when it isn't'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Test Every Substring

TimeO(n²)SpaceO(1)

Say it first to anchor the baseline and to surface the 'replacements = length − maxFreq' formula.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The answer is some substring. Given a substring, how many replacements does it take to make it uniform?

2Hint 2Explore hint

Count each letter's frequency in the substring; the cheapest unification keeps the most frequent letter, so cost = length − maxFreq.

3Hint 3Explore hint

For each start i and end j, compute that cost; if ≤ k, the substring is feasible. Track the longest feasible one.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "AABA", k = 1

i=0

"AABA": maxFreq(A)=3, cost 4−3=1 ≤ 1

Statefeasible, len 4

Final result4

C · Code with teaching comments

Reference implementation previewpublic int characterReplacement(String s, int k) { int n = s.length(); int best = 0; for (int i = 0; i < n; i++) { int[] count = new int[26];Explore the full code

solution.javaJava

Brute Force — Test Every Substring — reference

3 teaching notes

1
public int characterReplacement(String s, int k) {
2
    int n = s.length();
3
    int best = 0;
4
    for (int i = 0; i < n; i++) {
5
        // Fresh frequency table per start — the wasteful restart.
6
        int[] count = new int[26];
7
        int maxFreq = 0;
8
        for (int j = i; j < n; j++) {
9
            count[s.charAt(j) - 'A']++;
10
            // Most frequent letter so far in this window.
11
            maxFreq = Math.max(maxFreq, count[s.charAt(j) - 'A']);
12
            int windowLen = j - i + 1;
13
            // Replacements needed = windowLen − maxFreq; feasible when ≤ k.
14
            if (windowLen - maxFreq <= k) {
15
                best = Math.max(best, windowLen);
16
            }
17
        }
18
    }
19
    return best;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(1) space — There are O(n²) substrings; maintaining counts incrementally as j extends makes each O(1), so O(n²) time. A fixed 26-slot count array → O(1) space.

E · Edge cases and pitfalls3Recreating the count array per start — the quadratic cost.Explore edge cases

Pitfalls

Recreating the count array per start — the quadratic cost.
Computing cost as length − k instead of length − maxFreq.
Indexing past 26 if the input isn't strictly uppercase letters.

03.2

Approach 2 of 2 · Optimal

Sliding Window + Frequency Table (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Phrase it as 'one window, valid while windowLen − maxFreq ≤ k, shift left when it isn't'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Keep one window and a count of letters in it. The window is valid while (length − maxFreq) ≤ k.

2Hint 2Explore hint

Expand right by adding s[right] and updating maxFreq. If the window becomes invalid, move left forward by one (decrementing that letter's count).

3Hint 3Explore hint

A · Core idea

Why O(n) time and O(1) space. Each pointer sweeps the string once; the frequency table is constant size.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "AABABBA", k = 1

Array state

right=3

"AABA" maxFreq(A)=3, cost 1 ≤ 1, len 4

left ↓

[0]

[1]

[2]

right ↓

[3]

[4]

[5]

[6]

Current pointerResolved stateNot processed

Final result4

C · Code with teaching comments

solution.javaJava

Sliding Window + Frequency Table (Optimal) — optimal

4 teaching notes

1
public int characterReplacement(String s, int k) {
2
    int[] count = new int[26];
3
    int left = 0, maxFreq = 0, best = 0;
4
    for (int right = 0; right < s.length(); right++) {
5
        int idx = s.charAt(right) - 'A';
6
        count[idx]++;
7
        // Most frequent letter count; may stay stale after a shrink — intentionally.
8
        maxFreq = Math.max(maxFreq, count[idx]);
9
        // Replacements needed exceed budget → window invalid.
10
        if ((right - left + 1) - maxFreq > k) {
11
            count[s.charAt(left) - 'A']--;
12
            left++;
13
        }
14
        // Window length is the answer candidate, never maxFreq.
15
        best = Math.max(best, right - left + 1);
16
    }
17
    return best;
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — Both `left` and `right` move forward only, each at most n times → O(n) total. The frequency table is a fixed 26 ints → O(1) space.

E · Edge cases and pitfalls6s = "AAAA", k = 0 — Always uniform; cost 0 every step, window grows to full length 4.Explore edge cases

Edge cases handled

s = "AAAA", k = 0Always uniform; cost 0 every step, window grows to full length 4.
s = "ABCDE", k = 0Every 2-length window costs 1 > 0, so the window stays length 1 → answer 1.
s = "AAAB", k = 0Window "AAA" is valid (cost 0); adding B costs 1 > 0 so it slides → answer 3.

Pitfalls

Recomputing maxFreq by scanning all 26 counts on every shrink — works but unnecessary; the stale value is safe.
Returning maxFreq or maxFreq + k instead of the window length.
Using a while loop to shrink and then mismanaging maxFreq, producing a wrong (too-short) window.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong validity formula

The replacements needed to unify a window is its length minus the most frequent letter's count — not its length minus k.

Explore the code comparison

Don't write this

if (right - left + 1) - k > max_freq:
    ...

Write this instead

if (right - left + 1) - max_freq > k:
    count[ord(s[left]) - ord('A')] -= 1
    left += 1

Returning maxFreq instead of window length

The answer is the size of the longest achievable uniform window, which is right − left + 1, not the frequency of the dominant letter.

Explore the code comparison

Don't write this

best = Math.max(best, maxFreq);

Write this instead

best = Math.max(best, right - left + 1);

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sliding window; valid when windowLen − maxFreq ≤ k

Code pattern to memorize

count = [0]*26
left = 0
maxFreq = 0
best = 0
for right, c in enumerate(s):
    count[c] += 1
    maxFreq = max(maxFreq, count[c])
    while (right - left + 1) - maxFreq > k:
        count[s[left]] -= 1
        left += 1
    best = max(best, right - left + 1)
return best

Rules to remember

1Replacements needed = windowLength − maxFreq (keep the majority char, replace the rest).
2Window is valid iff that count ≤ k.
3Use an if (shift left by one) — the window never needs to shrink more than one step per expansion.
4You don't need to decrease maxFreq when shrinking; a stale-but-too-high maxFreq never produces a wrong larger answer.
5Answer is the largest valid window length seen — the window length itself, not maxFreq.

Use this pattern when

Longest window that becomes uniform/valid after at most k edits
Validity depends on the window length minus a frequency statistic
You can keep a frequency table and a running max frequency
A 'replace up to k' or 'flip up to k' contiguous-window question

Choose another pattern when

Replacements unlimited → answer is just the whole string length
Need zero repeats instead of all-same → Longest Substring Without Repeating
Counting subsequences, not contiguous windows → DP

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Longest Substring Without Repeating Characters
Variable window again, but validity is 'no repeats' via a last-index map.
Max Consecutive Ones III
Coming soon
Flip at most k zeros — window valid while zeros-in-window ≤ k; the binary special case.
Longest Substring with At Most K Distinct Characters
Coming soon
Window valid while the count map has at most k keys.
Minimum Window Substring
The shrinking-window cousin: grow to satisfy a need, then minimize.

Same pattern

←

Longest Substring Without Repeating Characters

Continue · Next problem

Minimum Window Substring