Definition
- Validity condition is
windowSize - maxFreq <= K, meaning the number of characters that differ from the dominant one does not exceed the replacement budget K. - Frequency array of size 26 tracks how many times each uppercase letter appears inside the current window.
- maxFreq high-water mark tracks the highest frequency of any single character in the window and is never decreased, which is safe because the answer only grows when a genuinely larger window appears.
- Single-step shrink advances the left pointer by at most one when the condition is violated, keeping the window size monotonically non-decreasing.
- Linear time is achieved because both pointers traverse the string once and no inner loop recomputes frequencies.
The National Bank of India has a string of daily status flags and can override at most K of them to make a run of identical flags, reporting the longest clean streak achievable. Picture a window over the flags. Inside it, the most common flag is the one you keep; every other flag needs overriding. As long as the overrides needed stay within budget K, you widen the window. If you would exceed K, you slide the left edge in by one.
Understanding the Concepts
What is the problem?
Given a string of uppercase letters and an integer K, find the length of the longest substring you can create with all identical characters by replacing at most K characters. For example, with "AABABBA" and K=1, the answer is 4 because you can replace the B at position 3 to get "AAAA".
package com.bank.dsa;
public class LongestRepeatingCharReplacement {
public static 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']);
if ((right - left + 1) - maxFreq > k) {
count[s.charAt(left) - 'A']--;
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}
}
Why does this matter in banking?
The National Bank of India tracks daily account status codes stored as a string of uppercase letters. The compliance team wants to know the longest streak that could be made uniform by correcting at most K mis-tagged entries. This measures data cleanliness and helps estimate the effort needed to fix status histories.
package com.bank.service;
import com.bank.dsa.LongestRepeatingCharReplacement;
public class StatusCleanlinessService {
public void analyze(String statusHistory, int maxCorrections) {
int longest = LongestRepeatingCharReplacement.characterReplacement(statusHistory, maxCorrections);
System.out.println("Status history: " + statusHistory);
System.out.println("Max corrections: " + maxCorrections);
System.out.println("Longest achievable uniform streak: " + longest);
}
public static void main(String[] args) {
new StatusCleanlinessService().analyze("AABABBA", 1);
}
}
Status history: AABABBA
Max corrections: 1
Longest achievable uniform streak: 4
How does the validity condition work?
The key insight is reframing the question. In any window, the cheapest way to make it uniform is to keep the most frequent character and replace all others. So the number of replacements needed equals windowSize - maxFreq. The window is feasible exactly when that quantity is at most K.
package com.bank.dsa;
public class ValidityDemo {
public static void main(String[] args) {
// Window "AABA": size=4, maxFreq(A)=3, replacements=4-3=1
String window = "AABA";
int[] count = new int[26];
int maxFreq = 0;
for (char c : window.toCharArray()) {
count[c - 'A']++;
maxFreq = Math.max(maxFreq, count[c - 'A']);
}
int replacements = window.length() - maxFreq;
System.out.println("Window: " + window);
System.out.println("Size: " + window.length() + ", maxFreq: " + maxFreq);
System.out.println("Replacements needed: " + replacements);
}
}
Window: AABA
Size: 4, maxFreq: 3
Replacements needed: 1
Why does maxFreq never decrease?
This is the famous subtlety. When a character leaves the window, the true maximum frequency might decrease, but the tracked maxFreq is kept as a high-water mark. This is safe because the best answer only grows when a larger valid window is found, which requires a genuinely higher frequency. A stale maxFreq can only let the window appear valid for sizes we already achieved, never produce a wrong larger answer.
package com.bank.dsa;
public class MaxFreqDemo {
public static void main(String[] args) {
String s = "AABABBA";
int k = 1;
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']);
if ((right - left + 1) - maxFreq > k) {
count[s.charAt(left) - 'A']--;
left++;
}
best = Math.max(best, right - left + 1);
System.out.println("right=" + right + " char=" + s.charAt(right)
+ " maxFreq=" + maxFreq + " windowSize=" + (right - left + 1) + " best=" + best);
}
}
}
right=0 char=A maxFreq=1 windowSize=1 best=1
right=1 char=A maxFreq=2 windowSize=2 best=2
right=2 char=B maxFreq=2 windowSize=3 best=3
right=3 char=A maxFreq=3 windowSize=4 best=4
right=4 char=B maxFreq=3 windowSize=4 best=4
right=5 char=B maxFreq=3 windowSize=4 best=4
right=6 char=A maxFreq=3 windowSize=4 best=4
What is the time and space complexity?
Time is O(n) because the right pointer moves once through the string and the left pointer only moves forward, with no inner loop to recompute the maximum frequency. Space is O(1) with a fixed-size frequency array of 26 entries for uppercase letters.
What are the edge cases?
When K is 0, no replacements are allowed, so the answer is the longest run of identical characters already present. When K is greater than or equal to the string length, the answer is the string length because you can replace everything. An empty string returns 0.
package com.bank.dsa;
public class EdgeCaseDemo {
public static void main(String[] args) {
System.out.println(LongestRepeatingCharReplacement.characterReplacement("AABABBA", 0)); // 2
System.out.println(LongestRepeatingCharReplacement.characterReplacement("AABABBA", 7)); // 7
System.out.println(LongestRepeatingCharReplacement.characterReplacement("", 3)); // 0
}
}
2
7
0
What are common mistakes?
The first mistake is trying to decrease maxFreq when a character leaves the window, which either adds an O(26) inner loop or breaks the invariant. The second mistake is shrinking the window by more than one step, which is unnecessary because the window grew by one this step. The third mistake is not updating maxFreq before checking the validity condition.
package com.bank.dsa;
public class CommonMistakesDemo {
// WRONG: tries to recompute maxFreq on every shrink
public static int slowVersion(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']++;
int maxF = 0;
for (int c : count) maxF = Math.max(maxF, c); // O(26) each step
while ((right - left + 1) - maxF > k) {
count[s.charAt(left) - 'A']--;
left++;
maxF = 0;
for (int c : count) maxF = Math.max(maxF, c); // O(26) again
}
best = Math.max(best, right - left + 1);
}
return best; // correct but slower due to inner O(26) scans
}
public static void main(String[] args) {
System.out.println(slowVersion("AABABBA", 1)); // 4 (correct but slower)
}
}
4
How is this different from the basic sliding window problems?
Unlike the longest substring without repeating characters where the window condition is simple uniqueness, this problem requires tracking frequency counts and using the clever maxFreq invariant. The non-decreasing maxFreq trick and the monotonic window size make this a harder problem that tests deeper understanding of sliding window mechanics.
What are common interview follow-up questions?
- What if the string contains lowercase letters too?
- How would you return the actual substring instead of just the length?
- What if you can replace at most K characters but each replacement has a cost?
- How does this relate to the minimum window substring problem?
Visual Overview
Input: "AABABBA", K=1
┌──────────────────────────────────────────────┐
│ Validity: windowSize - maxFreq <= K │
│ If window has 4 chars and maxFreq=3: │
│ replacements = 4 - 3 = 1 <= K=1 ── VALID │
└──────────────────────────────────────────────┘
Step 1: [A] maxFreq=1 size=1 1-1=0<=1 best=1
Step 2: [A,A] maxFreq=2 size=2 2-2=0<=1 best=2
Step 3: [A,A,B] maxFreq=2 size=3 3-2=1<=1 best=3
Step 4: [A,A,B,A] maxFreq=3 size=4 4-3=1<=1 best=4
Step 5: [A,B,A,B] maxFreq=3 size=4 4-2=2>1 shrink!
left++ ── [B,A,B] then add B
[B,A,B,B] size=4 best stays 4
Step 6: [A,B,B,A] size=4 best=4
Answer: 4
Key Takeaway
The Longest Repeating Character Replacement problem asks for the longest substring that can be made uniform by replacing at most K characters. The reframing that unlocks it is that in any window, the cheapest way to make it uniform is to keep the most frequent character and replace everything else. So the replacements needed equal windowSize - maxFreq, and the window is valid when that quantity is at most K.
Rajesh at the National Bank of India uses this on daily status code histories to estimate the longest clean streak achievable with at most K corrections. The algorithm maintains a sliding window with a frequency array, tracking the maximum frequency as a high-water mark that never decreases. When the window becomes invalid, the left pointer advances by exactly one, keeping the window size monotonically non-decreasing.
The famous subtlety is the non-decreasing maxFreq. It looks like a bug but is intentional: the best answer only grows when a genuinely larger window is found, which requires a truly higher frequency. A stale maxFreq can only let the window appear valid for sizes already achieved, never produce a wrong larger answer. This trick avoids an inner O(26) loop to recompute the true maximum on every step.
The whole algorithm runs in O(n) time with O(1) space over a fixed alphabet. When K is 0, the answer is simply the longest run of identical characters. When K exceeds the string length, the entire string can be made uniform.
Remember one sentence: a window is valid when its size minus the most frequent character count is at most K, and the non-decreasing maxFreq trick keeps it linear.
---