DSA-022 · FOCUSED PRACTICE
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:4AABA can become AAAA by changing its B. Later retained windows of length four need not themselves be feasible.
Input:
s="ABCDE", k=0
Output:1No 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.
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.
No unsaved text changes · 99/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
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.
- 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.
| 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.
- 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.
| 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:0No substring positions.
Input:
s="AAAA", k=0
Output:4Already uniform.
Input:
s="ABCD", k=100
Output:4At most budget, not exactly budget.
Input:
s="AABABBA", k=1
Output:4Exercises 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.