A telemetry cleaner, a barcode fixer, and a DNA-quality pass all ask the same question: what is the longest contiguous stretch that can be made one letter with at most k substitutions? The first version nested every slice: for each start i, grow j, count the majority letter, ask whether the rest fit in k replacements. A dozen-character SKU returned instantly. A night of event codes was still recounting every window when the job was killed.

Return the length of the longest substring that becomes one repeating letter after at most k replacements. A string already gives s.charAt(i) for free. Nested majority counts use that and still pay O(n²).

This is an interview writeup, not a sliding-window lecture. The sliding window post owns grow and shrink. Here we only care about when the window is still legal: length minus the majority count stays ≤ k. Longest Substring Without Repeating Characters is a unique window — a different invariant.

The problem

Given a String s of uppercase letters A–Z and an int k, you may replace at most k characters in a contiguous substring so the whole substring is one repeating letter. Return the length of the longest such substring. The empty string is length 0.

s = "ABAB",    k = 2  →  4   (replace both A's, or both B's)
s = "AABABBA", k = 1  →  4   ("AABA" → "AAAA", or "ABBA" with one replace)
s = "AAAA",    k = 2  →  4   (already one letter)
s = "ABCDE",   k = 0  →  1   (no replacements; longest run is 1)

Note: The replacements do not have to become a letter that already sits in the window — but the cheapest target is the current majority. Turning the rest into that letter costs windowLength − countOfMostFrequentChar. If that cost is ≤ k, the window is legal.

Nested majority counts are the honest brute force

For every start i, grow j and keep a 26-slot count plus a running majority. The slice [i..j] is legal when j - i + 1 - maxFreq ≤ k. Correct. Quadratic if the inner count is running; cubic if you recount from scratch.

int characterReplacementNested(String s, int k) {
    int best = 0;
    int n = s.length();
    for (int i = 0; i < n; i++) {
        int[] count = new int[26];
        int maxFreq = 0;
        for (int j = i; j < n; j++) {
            maxFreq = Math.max(maxFreq, ++count[s.charAt(j) - 'A']);
            if (j - i + 1 - maxFreq <= k) {
                best = Math.max(best, j - i + 1);
            }
        }
    }
    return best;
}

At n = 20 this is a rounding error. At a long event stream you paid a nested scan for a question a window answers in one pass: grow right; if the window needs more than k replacements, shrink left.

Right grows; left shrinks when replacements exceed k

Two indexes, both only forward. right is the next character that wants in. Increment its bucket and raise maxFreq if this character is now the majority. The window needs right - left + 1 - maxFreq replacements. While that is > k, decrement the leaving character and move left. Then best = max(best, windowLength). You never restart from 0.

Walk "AABABBA" with k = 1:

s = A A B A B B A
    0 1 2 3 4 5 6
k = 1

right=0 c=A  maxFreq=1  len=1  need=0  [A]     best=1
right=1 c=A  maxFreq=2  len=2  need=0  [AA]    best=2
right=2 c=B  maxFreq=2  len=3  need=1  [AAB]   best=3
right=3 c=A  maxFreq=3  len=4  need=1  [AABA]  best=4
right=4 c=B  maxFreq=3  len=5  need=2  shrink A, left=1  [ABAB]  best=4
right=5 c=B  maxFreq=3  len=5  need=2  shrink A, left=2  [BABB]  best=4
right=6 c=A  maxFreq=3  len=5  need=2  shrink B, left=3  [ABBA]  best=4

"AABA" (indexes 0..3) is the first length-4 hit: one B, k = 1. "BABB" and "ABBA" also score 4. Nothing longer fits.

The Java is that walk:

int characterReplacement(String s, int k) {
    int[] count = new int[26];
    int left = 0;
    int maxFreq = 0;
    int best = 0;
    for (int right = 0; right < s.length(); right++) {
        maxFreq = Math.max(maxFreq, ++count[s.charAt(right) - 'A']);
        while (right - left + 1 - maxFreq > k) {
            count[s.charAt(left) - 'A']--;
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Time is O(n) — one pass, each index enters and leaves at most once. Space is O(1) for 26 buckets. Empty input never enters the loop; best stays 0.

Note: After the shrink at right = 4, live counts are A:2 and B:2, but maxFreq stays 3. That is an upper bound, not the live majority. Recomputing maxFreq from the 26 buckets on every shrink is correct and still O(n). Skipping it is also correct here: best only grows, and a smaller majority cannot produce a longer legal window than one you already scored when maxFreq last rose. A stale-high maxFreq may leave an actually-illegal slice in place ( [ABAB] needs two replacements), but that slice is not a new record — "AABA" already scored 4. Do not treat a stale maxFreq as the live majority if a follow-up asks you to name the letter you would keep.

What interviewers usually poke next

  • Return the substring, not the length. Keep a pair of best endpoints while you already compute right - left + 1. Same pass.
  • Why not decrement maxFreq. Say the upper-bound argument out loud. If they want the live majority, scan 26 buckets on shrink — same asymptotics, easier to defend.
  • k = 0. The window may not replace anything: answer is the longest run of a single letter.
  • Alphabet. int[26] is legal for uppercase A–Z. Lowercase is 'a'. Unicode wants a map; 26 slots are not a Unicode solution.
  • Later window family. Minimum Window Substring still grows and shrinks, but the invariant is cover a target, not spare k mismatches. Do not solve it here.
  • Null. Production would reject. At the board, ask.

You are done with this problem when you can say, out loud, why nested majority checks are correct, why the window is legal while length minus majority count stays ≤ k, and why a stale maxFreq still cannot beat the best length you already recorded.