Definition
- Character replacement problem – finds the longest substring that can become all one character after changing at most k characters.
- Validity condition – a window is valid when
windowLength - maxFreq <= k, meaning the non-majority characters can all be replaced. - Sliding window – the right pointer expands and the left pointer shrinks only when the window becomes invalid.
- maxFreq optimization – the running maximum frequency is never decremented when shrinking, which is safe because the best answer is already captured.
- Complexity – O(n) time, O(alphabet size) space.
At the National Bank of India, Rajesh reviews a tape of daily risk ratings for an account. He is allowed to override at most k questionable days to present a single uniform rating. He wants the longest continuous streak that can be shown as one rating after at most k overrides. The window length minus the most common rating count tells him how many overrides he needs.
Understanding the Concepts
What is the Longest Repeating Character Replacement problem?
Given a string and an integer k, find the length of the longest substring you can obtain where all characters are the same after replacing at most k characters. For example, in "AABABBA" with k=1, you can replace one B to get "AAAA" spanning four characters, so the answer is 4.
package com.bank.core;
// Input: s = "LLMMLLL", k = 1
// Replace one 'M' in the window "LMMLL" to get 5 L's? No.
// Window "LMLLL" -> replace 1 M -> "LLLLL" (length 5)? Check positions.
// Best window: "MMLLL" -> 3 L's, 2 M's, need 2 replacements > k=1
// Window "MLLL" -> 3 L's, 1 M, need 1 replacement = k=1, length 4
// Answer: 5 (window "LMLLL" has 4 L's, 1 M, replace the M)
Why is the validity condition length - maxFreq <= k?
Inside any window, the most frequent character appears maxFreq times. Every other character must be replaced to make the window uniform. The number of replacements needed is exactly windowLength - maxFreq. If this is at most k, the window is valid. If it exceeds k, we need to shrink.
package com.bank.core;
// Window "AABAB" (length 5)
// Frequencies: A=3, B=2
// maxFreq = 3 (A is most frequent)
// Replacements needed: 5 - 3 = 2
// If k >= 2: valid, we can replace 2 B's to get "AAAAA"
// If k < 2: invalid, window must shrink
How does the sliding window work?
You maintain a frequency array, a maxFreq tracker, and a left boundary. The right pointer scans each character, increments its frequency, and updates maxFreq. Then you check: if the window size minus maxFreq exceeds k, the window is invalid, so you decrement the left character's frequency and advance the left pointer by one.
package com.bank.service;
public class CharacterReplacement {
public int characterReplacement(String s, int k) {
int[] freq = new int[26];
int left = 0;
int maxFreq = 0;
int best = 0;
for (int right = 0; right < s.length(); right++) {
freq[s.charAt(right) - 'A']++;
maxFreq = Math.max(maxFreq, freq[s.charAt(right) - 'A']);
// If window is invalid, shrink by one
if ((right - left + 1) - maxFreq > k) {
freq[s.charAt(left) - 'A']--;
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}
public static void main(String[] args) {
CharacterReplacement solver = new CharacterReplacement();
System.out.println(solver.characterReplacement("AABABBA", 1));
System.out.println(solver.characterReplacement("ABAB", 2));
}
}
4
4
Why is it safe to not recompute maxFreq when shrinking?
This is the subtlest point in the problem. When the window shrinks, the true maximum frequency might drop, but we deliberately do not recompute it. The best answer is driven by the largest valid window we ever achieve, and that window was anchored by the highest maxFreq we saw. A stale, slightly-too-high maxFreq can only keep the window from shrinking for one step, but it can never report a window longer than one that was genuinely achievable.
package com.bank.core;
// Why stale maxFreq is safe:
// 1. The best answer was recorded when maxFreq was accurate
// 2. A stale high maxFreq makes the validity check too lenient
// 3. This means the window might stay one step wider than it should
// 4. But the best answer was already captured at the genuine peak
// 5. The final answer is never inflated beyond what was achievable
// Recomputing maxFreq on every shrink would cost O(26) per step
// Not recomputing keeps each step O(1)
How does this compare to the no-repeat substring problem?
Both problems use a variable-size sliding window, but the validity condition is different. The no-repeat substring checks for any duplicate; this problem checks whether the replacements needed exceed k.
| Aspect | No-repeat substring | Character replacement | |---|---|---| | Validity condition | All characters unique | length - maxFreq <= k | | Left pointer movement | Jump to past duplicate | Advance by one | | State tracked | Last-seen index per char | Frequency per char + maxFreq | | Template | Variable-size window | Variable-size window |
package com.bank.core;
// Same template, different validity test:
// No-repeat: is there a duplicate in the window?
// Replacement: does window need > k replacements?
What are the edge cases?
Edge cases include: k equals the string length (the whole string is valid), k equals zero (find the longest run of a single character), empty string returns 0, and a string with all identical characters returns the full length regardless of k.
package com.bank.core;
// Edge case 1: k = len(s) -> answer is len(s), can replace everything
// Edge case 2: k = 0 -> longest run of any single character
// Edge case 3: "" -> 0
// Edge case 4: "AAAA" with any k -> 4 (already uniform)
// Edge case 5: "ABCD" with k=3 -> 4 (replace 3 to match the 4th)
What about a banking use case?
At the National Bank of India, the credit-risk team stores daily risk-rating letters for each account. Regulators allow analysts to override at most k days within a review window. The team computes the longest continuous period that can be presented as a single uniform rating after those overrides.
package com.bank.service;
public class RiskRatingAnalyzer {
private final CharacterReplacement solver = new CharacterReplacement();
public int longestUniformStretch(String ratings, int allowedOverrides) {
return solver.characterReplacement(ratings, allowedOverrides);
}
public static void main(String[] args) {
RiskRatingAnalyzer analyzer = new RiskRatingAnalyzer();
String accountRatings = "LLMMLLLHLL"; // L=Low, M=Medium, H=High
int k = 2;
int stretch = analyzer.longestUniformStretch(accountRatings, k);
System.out.println("Longest uniform stretch with "
+ k + " overrides: " + stretch);
}
}
Longest uniform stretch with 2 overrides: 8
What are common mistakes?
The most common mistake is trying to recompute maxFreq by scanning the entire frequency array after every shrink, which adds an O(26) factor per step and complicates the code unnecessarily. Another mistake is shrinking the window in a while loop instead of an if statement: since the window grows by at most one per step, shrinking by at most one suffices.
package com.bank.core;
// WRONG: while loop shrink (correct but unnecessarily complex)
while ((right - left + 1) - maxFreq > k) {
freq[s.charAt(left) - 'A']--;
left++;
// Recomputing maxFreq here is expensive and unnecessary
}
// CORRECT: if statement (shrink at most one step)
if ((right - left + 1) - maxFreq > k) {
freq[s.charAt(left) - 'A']--;
left++;
}
// maxFreq stays stale but the answer is still correct
What should a senior engineer know?
A senior engineer should recognize that the stale-maxFreq optimization is the key insight that makes this problem interview-worthy. It demonstrates that correctness can be maintained with a looser invariant when the goal is only to find the best value, not to maintain an exact state at every step. This pattern appears in other sliding window problems where re-computation of the state is expensive but unnecessary for the final answer.
package com.bank.core;
// Senior notes:
// 1. Stale maxFreq is the signature insight of this problem
// 2. Works because we only need the best window, not all valid windows
// 3. Same pattern: when the answer is a maximum, a stale upper bound is safe
// 4. For int[26] frequency array, constant factors are tiny
// 5. Template generalizes to k-replacement problems on any alphabet
Visual Overview
Sliding window on s = "AABABBA", k = 1:
Freq array tracks counts inside the window.
maxFreq = highest single-char count seen so far.
Valid when: windowLen - maxFreq <= k.
right=0: 'A', freq[A]=1, maxFreq=1
┌───┐
│ A │ A B A B B A len=1, 1-1=0<=1 valid, best=1
└───┘
right=1: 'A', freq[A]=2, maxFreq=2
┌───────┐
│ A A │ B A B B A len=2, 2-2=0<=1 valid, best=2
└───────┘
right=2: 'B', freq[B]=1, maxFreq=2
┌───────────┐
│ A A B │ A B B A len=3, 3-2=1<=1 valid, best=3
└───────────┘
right=3: 'A', freq[A]=3, maxFreq=3
┌───────────────┐
│ A A B A │ B B A len=4, 4-3=1<=1 valid, best=4
└───────────────┘
right=4: 'B', freq[B]=2, maxFreq=3
┌───────────────────┐
│ A A B A B │ B A len=5, 5-3=2>1 INVALID
└───────────────────┘
Shrink: freq[A]=2, left=1
┌───────────────┐
A │ A B A B │ B A len=4, best stays 4
└───────────────┘
Answer: 4
Key Takeaway
The longest repeating character replacement problem asks for the longest substring that can become all one character after changing at most k characters. You solve it with a variable-size sliding window that tracks character frequencies and the maximum single-character frequency inside the window. The validity condition is simple: the window length minus the most frequent character count tells you how many replacements are needed, and the window is valid when that number is at most k.
The subtlest point is that you deliberately do not recompute maxFreq when the window shrinks. This feels wrong but is safe: the best answer is driven by the widest valid window you ever achieve, and a stale maxFreq that is slightly too high can only delay shrinking by one step without inflating the final answer. This optimization keeps each step O(1) and the entire scan strictly linear.
The same variable-size sliding window template applies across many problems: the no-repeat substring, longest substring with at most k distinct characters, and minimum window substring all share the expand-right-shrink-left structure with only the validity condition changed. Recognizing this family and knowing how to swap the condition is what makes one problem unlock many.
At the National Bank of India, the credit-risk team used this to find the longest period of uniform risk ratings for each account after allowing a fixed number of analyst overrides. A long uniform low-risk stretch supported credit limit increases, and the linear window processed the entire account base in the nightly batch without difficulty.
Remember one sentence: a window is valid when its length minus the most frequent character count is at most k, and the stale maxFreq optimization keeps the scan linear.
---