Longest Repeating Character Replacement: Window Where size − maxFreq ≤ K

• Validity rule is windowSize - maxFreq <= K, where maxFreq is the count of the most frequent character in the window.
• Non-decreasing maxFreq is the famous trick: the tracked maximum frequency never decreases even when characters leave, which is safe because the answer only grows with a genuinely larger window.
• Single-step shrink advances the left pointer by at most one when the condition is violated, keeping the window monotonically non-decreasing.
• Frequency array of size 26 tracks character counts with O(1) lookups.
• O(n) time because both pointers traverse the string once and no inner loop rescans frequencies.

What is the problem?

Given a string of uppercase letters and an integer K, find the length of the longest substring you can make uniform by replacing at most K characters. This is the same problem as Q1446, presented with a focus on the non-decreasing maxFreq invariant and why the single-step shrink keeps the algorithm correct.

package com.bank.dsa;

public class CharReplacementV2 {
    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 the non-decreasing maxFreq work?

This is the most asked follow-up. When a character leaves the window, its count decreases, so the true maximum frequency might drop. But we deliberately keep maxFreq at its highest value ever seen. The key insight is that the best answer can only increase when a larger window is found valid, and a larger window requires a genuinely higher frequency. A stale maxFreq might let the current window appear valid at sizes we already achieved, but it cannot create a new best that is wrong.

package com.bank.dsa;

public class MaxFreqInvariantDemo {
    public static void main(String[] args) {
        String s = "AABBC";
        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']);
            int windowSize = right - left + 1;
            boolean valid = (windowSize - maxFreq) <= k;
            if (!valid) {
                count[s.charAt(left) - 'A']--;
                left++;
                windowSize--;
            }
            best = Math.max(best, right - left + 1);
            System.out.println("right=" + right + " maxFreq=" + maxFreq
                + " windowSize=" + (right - left + 1) + " valid=" + valid + " best=" + best);
        }
    }
}

right=0 maxFreq=1 windowSize=1 valid=true best=1
right=1 maxFreq=2 windowSize=2 valid=true best=2
right=2 maxFreq=2 windowSize=3 valid=true best=3
right=3 maxFreq=2 windowSize=3 valid=false best=3
right=4 maxFreq=2 windowSize=3 valid=false best=3

Why does single-step shrink work?

Since the window grew by one this step (right moved forward), shrinking by at most one from the left keeps the window size from ever decreasing. The window is effectively maintained at a floor equal to the best size found so far. Once you have found a window of size 4, the window never shrinks below 4; it stays the same or grows.

package com.bank.dsa;

public class MonotonicWindowDemo {
    public static void main(String[] args) {
        String s = "AABABBA";
        int k = 1;
        int[] count = new int[26];
        int left = 0, maxFreq = 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++;
            }
            System.out.println("Window size: " + (right - left + 1));
        }
        // Window size never decreases
    }
}

Window size: 1
Window size: 2
Window size: 3
Window size: 4
Window size: 4
Window size: 4
Window size: 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 moves forward at most once per step, with no inner loop. Space is O(1) with a fixed 26-element frequency array 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. When K is greater than or equal to the string length, the entire string can be made uniform. When all characters are already the same, the answer is the string length regardless of K.

package com.bank.dsa;

public class EdgeCaseDemo {
    public static void main(String[] args) {
        System.out.println(CharReplacementV2.characterReplacement("AABABBA", 0)); // 2
        System.out.println(CharReplacementV2.characterReplacement("ABC", 3));     // 3
        System.out.println(CharReplacementV2.characterReplacement("AAAA", 0));    // 4
        System.out.println(CharReplacementV2.characterReplacement("", 5));         // 0
    }
}

2
3
4
0

What are common mistakes?

The first mistake is trying to decrease maxFreq, which either adds an O(26) recomputation loop or breaks the invariant. The second mistake is using a while loop to shrink multiple times when one step is sufficient. The third mistake is checking the validity condition after updating best instead of before.

How is this related to other sliding window problems?

This problem is harder than the basic unique-substring window because the validity condition involves frequency tracking and the non-decreasing maxFreq trick. The minimum window substring problem uses a similar frequency map but has a different structure: it minimizes the window rather than maximizing it.

What are common interview follow-up questions?

• What if the string contains both uppercase and lowercase letters?
• How would you return the actual longest substring?
• What if K can be negative (you must keep certain characters unchanged)?
• How does this generalize to the longest substring with at most K distinct characters?