DSA-022 · Historical-frequency maximum-length window

Longest Repeating Character Replacement

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 13125 deterministic checks. Learner drafts are not executed.

Understand the problem

Return the longest substring length that can be made one repeated uppercase letter using at most k replacements.

s is non-null with 0–100,000 ASCII uppercase A–Z characters. k is a nonnegative int, including Integer.MAX_VALUE. Other alphabets and negative budgets are outside the contract.
Return a length only. A replacement changes one position to any uppercase letter, and at most k positions may change. Empty input returns 0; a budget larger than the string length is allowed.
Preserve s. The optimized implementation keeps a historical maximum frequency that may exceed the true maximum in its current window. Its retained interval is not promised to be a valid witness; only the returned maximum length is guaranteed.

Examples

Input: s="AABABBA", k=1
Output: 4
AABA can become AAAA by changing its B. Later retained windows of length four need not themselves be feasible.
Input: s="ABCDE", k=0
Output: 1
No changes are available, so only an already-uniform run qualifies.

Before you start

Contiguous windows, inclusive bounds, and empty intervals
Java frequency arrays and loop-invariant reasoning

Recognize the structure

For a particular window, the exact cost is length minus its largest current frequency. A length-only objective permits a historical frequency bound, but this shortcut needs a stronger argument than claiming every current window is valid.

Try before revealing

Hint 1

For one window, how many positions differ from its dominant character?

Hint 2

What does a historical maximum allow you to reject safely?

Hint 3

Keep the historical count for length only, and explain why each new record length has an earlier feasible witness.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Enumerate with an exact dominant count

For each left boundary, grow right while maintaining fresh counts and the exact maximum. Test length-dominant≤k. For ABBA with k=1, AB costs one, ABB costs one, and ABBA costs two, so this start contributes length three. The baseline checks every start in O(n²) time and O(26) space and always reasons about genuinely feasible windows.

Improve the baseline

Start with the exact cost

Making a window uniform is cheapest when its most frequent character is retained. Every other position must change, so the exact cost is length-currentMax.

Retain a historical bound

When adding a character, update historicalMax from its new count; never decrease it on removal. If length-historicalMax>k, move left once. Window length can increase by at most one per new right, so one shrink restores this relaxed inequality.

Track only the greatest length

With one shrink, retained length never decreases. Record that length as best, but do not return its endpoints as a witness. Trace both currentMax and historicalMax so a stale bound is visible.

Why it is correct

State and safe rejection

Counts exactly describe the retained interval; historicalMax is the largest count observed during expansion and is at least its true maximum. Therefore length-historicalMax>k implies actual infeasibility. A left boundary of an optimal window cannot be discarded before that window’s right endpoint: every prefix within that optimal window is feasible, so it cannot trigger this rejection.

Why a record length is achievable

When historicalMax rises to M, the new window is genuinely feasible: the previous retained length was at most oldM+k and expansion raises both length and M by at most one. With M fixed, length can grow without removing those M occurrences until reaching M+k. After any shrink at that cap, length stays at the already-achieved cap until M rises again. Thus every new record length has a feasible witness, even if later equal-length retained intervals do not.

Optimality and termination

Safe rejection prevents losing an optimum, so the greatest retained length is at least optimal. The record-length argument prevents overestimation, so it is at most optimal. right advances once per iteration and left never retreats; the returned length is exact.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

public final class Solution {
    public static int characterReplacement(String s, int k) {
        int[] counts = new int[26];
        int left = 0, historicalMax = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            historicalMax = Math.max(historicalMax, ++counts[s.charAt(right) - 'A']);
            if (right - left + 1 - historicalMax > k) counts[s.charAt(left++) - 'A']--;
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
    public static int baseline(String s, int k) {
        int best = 0;
        for (int left = 0; left < s.length(); left++) {
            int[] counts = new int[26]; int dominant = 0;
            for (int right = left; right < s.length(); right++) {
                dominant = Math.max(dominant, ++counts[s.charAt(right) - 'A']);
                if (right - left + 1 - dominant <= k) best = Math.max(best, right - left + 1);
            }
        }
        return best;
    }
}

Read the meaningful blocks

Update only the entered count

Only one frequency increases on expansion, so comparing that frequency with historicalMax is sufficient.

Use a single if deliberately

This is a nondecreasing-length algorithm with a relaxed historical bound. It is not the generic shrink-until-currently-valid template.

No witness endpoints

For AABABBA,k=1, a later retained ABAB has true cost two but historicalMax three. A caller must not treat that retained interval as a valid one-replacement answer.

Complexity

O(n+26) time and O(26) auxiliary space, constant for the declared uppercase alphabet. Each right addition causes at most one left removal.

The exact baseline costs O(n²+26n) time and O(26) workspace. Recomputing an exact maximum over 26 slots after removals also yields a simpler O(26n) alternative when valid current endpoints are needed.

Exact-state walkthroughs

Reveal normal and boundary traces

Historical and true maxima diverge

Input: {"s":"AABABBA","k":1} · Result: 4

Step 1 of 9: Begin with an empty retained interval.

Counts describe the current window, while the historical bound starts at zero.

Original text — highlighted retained interval

0: "A"
1: "A"
2: "B"
3: "A"
4: "B"
5: "B"
6: "A"

Current dominant count: 0. Historical maximum: 0. Actual replacements needed now: 0. The current counts and historical bound are shown separately.

State after this step
Variable	Value
text	`"AABABBA"`
left	`0`
right	`-1`
window	`""`
counts	`[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]`
historicalMax	`0`
currentMax	`0`
trueCost	`0`
best	`0`

See the affected Java block

 1 public final class Solution {
 2     public static int characterReplacement(String s, int k) {
 3         int[] counts = new int[26];
 4         int left = 0, historicalMax = 0, best = 0;
 5         for (int right = 0; right < s.length(); right++) {
 6             historicalMax = Math.max(historicalMax, ++counts[s.charAt(right) - 'A']);
 7             if (right - left + 1 - historicalMax > k) counts[s.charAt(left++) - 'A']--;
 8             best = Math.max(best, right - left + 1);
 9         }
10         return best;
11     }
12     public static int baseline(String s, int k) {
13         int best = 0;
14         for (int left = 0; left < s.length(); left++) {
15             int[] counts = new int[26]; int dominant = 0;
16             for (int right = left; right < s.length(); right++) {
17                 dominant = Math.max(dominant, ++counts[s.charAt(right) - 'A']);
18                 if (right - left + 1 - dominant <= k) best = Math.max(best, right - left + 1);
19             }
20         }
21         return best;
22     }
23 }
24

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Begin with an empty retained interval.
Counts describe the current window, while the historical bound starts at zero.
text
"AABABBA"
left
0
right
-1
window
""
counts
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
historicalMax
0
currentMax
0
trueCost
0
best
0
Expand, optionally shrink once, and record the greatest retained length.
The relaxed bound is satisfied. A stale historical maximum can retain an invalid current window; best is justified by an achievable record length, not these current endpoints.
text
"AABABBA"
left
0
right
0
window
"A"
counts
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
historicalMax
1
currentMax
1
trueCost
0
best
1
oldLeft
0
relaxedCost
0
currentlyFeasible
true
Expand, optionally shrink once, and record the greatest retained length.
The relaxed bound is satisfied. A stale historical maximum can retain an invalid current window; best is justified by an achievable record length, not these current endpoints.
text
"AABABBA"
left
0
right
1
window
"AA"
counts
[2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
historicalMax
2
currentMax
2
trueCost
0
best
2
oldLeft
0
relaxedCost
0
currentlyFeasible
true
Expand, optionally shrink once, and record the greatest retained length.
The relaxed bound is satisfied. A stale historical maximum can retain an invalid current window; best is justified by an achievable record length, not these current endpoints.
text
"AABABBA"
left
0
right
2
window
"AAB"
counts
[2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
historicalMax
2
currentMax
2
trueCost
1
best
3
oldLeft
0
relaxedCost
1
currentlyFeasible
true
Expand, optionally shrink once, and record the greatest retained length.
The relaxed bound is satisfied. A stale historical maximum can retain an invalid current window; best is justified by an achievable record length, not these current endpoints.
text
"AABABBA"
left
0
right
3
window
"AABA"
counts
[3,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
historicalMax
3
currentMax
3
trueCost
1
best
4
oldLeft
0
relaxedCost
1
currentlyFeasible
true
Expand, optionally shrink once, and record the greatest retained length.
The relaxed bound is satisfied. A stale historical maximum can retain an invalid current window; best is justified by an achievable record length, not these current endpoints.
text
"AABABBA"
left
1
right
4
window
"ABAB"
counts
[2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
historicalMax
3
currentMax
2
trueCost
2
best
4
oldLeft
0
relaxedCost
1
currentlyFeasible
false
Expand, optionally shrink once, and record the greatest retained length.
The relaxed bound is satisfied. A stale historical maximum can retain an invalid current window; best is justified by an achievable record length, not these current endpoints.
text
"AABABBA"
left
2
right
5
window
"BABB"
counts
[1,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
historicalMax
3
currentMax
3
trueCost
1
best
4
oldLeft
1
relaxedCost
1
currentlyFeasible
true
Expand, optionally shrink once, and record the greatest retained length.
The relaxed bound is satisfied. A stale historical maximum can retain an invalid current window; best is justified by an achievable record length, not these current endpoints.
text
"AABABBA"
left
3
right
6
window
"ABBA"
counts
[2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
historicalMax
3
currentMax
2
trueCost
2
best
4
oldLeft
2
relaxedCost
1
currentlyFeasible
false
Return the contract result.
The result follows the declared empty, ordering, tie, and mutation rules.
result
4

Zero budget cannot bridge a mismatch

Input: {"s":"ABBA","k":0} · Result: 2

Step 1 of 6: Begin with an empty retained interval.

Counts describe the current window, while the historical bound starts at zero.

Original text — highlighted retained interval

0: "A"
1: "B"
2: "B"
3: "A"

Current dominant count: 0. Historical maximum: 0. Actual replacements needed now: 0. The current counts and historical bound are shown separately.

State after this step
Variable	Value
text	`"ABBA"`
left	`0`
right	`-1`
window	`""`
counts	`[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]`
historicalMax	`0`
currentMax	`0`
trueCost	`0`
best	`0`

See the affected Java block

 1 public final class Solution {
 2     public static int characterReplacement(String s, int k) {
 3         int[] counts = new int[26];
 4         int left = 0, historicalMax = 0, best = 0;
 5         for (int right = 0; right < s.length(); right++) {
 6             historicalMax = Math.max(historicalMax, ++counts[s.charAt(right) - 'A']);
 7             if (right - left + 1 - historicalMax > k) counts[s.charAt(left++) - 'A']--;
 8             best = Math.max(best, right - left + 1);
 9         }
10         return best;
11     }
12     public static int baseline(String s, int k) {
13         int best = 0;
14         for (int left = 0; left < s.length(); left++) {
15             int[] counts = new int[26]; int dominant = 0;
16             for (int right = left; right < s.length(); right++) {
17                 dominant = Math.max(dominant, ++counts[s.charAt(right) - 'A']);
18                 if (right - left + 1 - dominant <= k) best = Math.max(best, right - left + 1);
19             }
20         }
21         return best;
22     }
23 }
24

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Begin with an empty retained interval.
Counts describe the current window, while the historical bound starts at zero.
text
"ABBA"
left
0
right
-1
window
""
counts
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
historicalMax
0
currentMax
0
trueCost
0
best
0
Expand, optionally shrink once, and record the greatest retained length.
The relaxed bound is satisfied. A stale historical maximum can retain an invalid current window; best is justified by an achievable record length, not these current endpoints.
text
"ABBA"
left
0
right
0
window
"A"
counts
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
historicalMax
1
currentMax
1
trueCost
0
best
1
oldLeft
0
relaxedCost
0
currentlyFeasible
true
Expand, optionally shrink once, and record the greatest retained length.
The relaxed bound is satisfied. A stale historical maximum can retain an invalid current window; best is justified by an achievable record length, not these current endpoints.
text
"ABBA"
left
1
right
1
window
"B"
counts
[0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
historicalMax
1
currentMax
1
trueCost
0
best
1
oldLeft
0
relaxedCost
0
currentlyFeasible
true
Expand, optionally shrink once, and record the greatest retained length.
The relaxed bound is satisfied. A stale historical maximum can retain an invalid current window; best is justified by an achievable record length, not these current endpoints.
text
"ABBA"
left
1
right
2
window
"BB"
counts
[0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
historicalMax
2
currentMax
2
trueCost
0
best
2
oldLeft
1
relaxedCost
0
currentlyFeasible
true
Expand, optionally shrink once, and record the greatest retained length.
The relaxed bound is satisfied. A stale historical maximum can retain an invalid current window; best is justified by an achievable record length, not these current endpoints.
text
"ABBA"
left
2
right
3
window
"BA"
counts
[1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
historicalMax
2
currentMax
1
trueCost
1
best
2
oldLeft
1
relaxedCost
0
currentlyFeasible
false
Return the contract result.
The result follows the declared empty, ordering, tie, and mutation rules.
result
2

Test the contract

Input: s="", k=0
Output: 0
No substring positions.
Input: s="AAAA", k=0
Output: 4
Already uniform.
Input: s="ABCD", k=100
Output: 4
At most budget, not exactly budget.
Input: s="AABABBA", k=1
Output: 4
Exercises a stale historical maximum.

Common mistakes and counterexamples

Claim every retained window is feasible

Counterexample: AABABBA,k=1 retains ABAB with length four and historicalMax three even though currentMax is two.

Use the record-length proof; report the true maximum separately in traces.

Decrease the historical maximum by one on removal

Counterexample: The departing symbol may not be a unique mode, and a maximum is not a simple counter.

Either keep the historical bound with its proof or recompute an exact maximum.

Use lowercase indices with uppercase storage

Counterexample: a minus A is outside a 26-slot uppercase alphabet.

Declare A–Z explicitly or redesign symbol storage.

Follow-ups

Return a valid substring.

Maintain exact counts and recompute the current maximum while shrinking until truly feasible. Save boundaries only for those valid windows. The fixed alphabet keeps O(26n) linear time without reusing the stale-window witness incorrectly.

Require exactly k changed positions.

Specify whether a replacement must change the symbol and whether changes may be repeated. If exactly k distinct positions must end changed, feasibility depends on the chosen target count, not merely the at-most-k optimum.

Use an arbitrary alphabet.

A map can store counts, but recomputing a mode is no longer a constant 26-slot scan. Separate expected map cost, historical-length reasoning, and the data structure needed for exact window queries.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 99/20,000 characters

Self-review

I distinguish true and historical frequency.I prove the length without claiming a current witness.I know when exact maximum maintenance is needed.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Sliding windows: define validity first

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-15 · Original teaching content, examples, and Java implementations authored for AceYourInterviews. These standard algorithmic tasks carry no company-frequency or interview-outcome claims.