Longest Repeating Character Replacement

MEDIUM✓ CHIP-TIMEDLC #424 — FULL STATEMENT ↗

The drill: With a budget of k rewrites, find the longest stretch of an uppercase string you could turn into one repeated letter. The move is scoring a window by what unifying it would cost: length minus its majority count.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An uppercase string and a rewrite budget k arrive together, and the task is to find the length of the longest contiguous stretch that could be turned into one single repeated letter using at most k character swaps within that stretch.

A rewrite budget spent within one candidate stretch doesn't carry over to another — each stretch is judged independently on how many of its own characters would need changing to make every character match its own most common letter.

Only the longest achievable length is reported; which letter the stretch would become, or which characters get swapped, doesn't need to be named.

EX 01

s = "AABAB" · k = 1

→ 4

PATCH ONE B, FRONT FOUR BECOME AAAA

EX 02

s = "ABBB" · k = 2

→ 4

BUDGET COVERS THE LONE A WITH ROOM TO SPARE

EX 03

s = "ABCDE" · k = 1

→ 2

ALL DISTINCT — ONE REWRITE BUYS LENGTH TWO

string length runs from zero up to around one hundred thousand characters
input contains only uppercase English letters
the rewrite budget k is non-negative and can be zero
only the longest achievable length is reported, not the resulting string

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Instead of imagining edits, score a window: how many characters inside are NOT its most common letter? That count is exactly the rewrites the window needs.

HINT 2 THE STRUCTURE

A window is affordable while length − maxCount ≤ k, so grow the right edge and only worry when the budget is blown.

HINT 3 ONE STEP FROM THE ANSWER

Keep 26 counts plus the largest count ever seen; on overspend, slide left by one instead of collapsing. A stale max can't hurt — the window never shrinks below the best length already banked.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE BUDGETED WINDOWPATTERN · SLIDING WINDOW + BUDGETs = "AABAB" · k = 1

LETTER COUNTS (WINDOW)

— empty —

STEP 1

Budget k=1. Grow the window; it stays affordable while length minus the top letter count is ≤ 1.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/longest-repeating-character-replacement.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        counts = {}
        best = 0
        left = 0
        top = 0  # largest count ever seen in the window (may go stale — safely)
        for right, c in enumerate(s):
            counts[c] = counts.get(c, 0) + 1
            top = max(top, counts[c])
            if (right - left + 1) - top > k:
                counts[s[left]] -= 1    # over budget: slide, don't shrink
                left += 1
            best = max(best, right - left + 1)
        return best

TIME O(N)SPACE O(26)PYTHON · RACE PACE · 14 LN

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        best = 0
        n = len(s)
        for start in range(n):
            counts = {}
            top = 0
            for end in range(start, n):
                c = s[end]
                counts[c] = counts.get(c, 0) + 1
                top = max(top, counts[c])
                length = end - start + 1
                if length - top <= k:
                    best = max(best, length)
                else:
                    break   # the deficit only grows from here
        return best

TIME O(N²)SPACE O(26)PYTHON · TRAINING PACE · 17 LN

class Solution {
    public int characterReplacement(String s, int k) {
        int[] counts = new int[26];
        int best = 0, left = 0;
        int top = 0; // largest count ever seen in the window (may go stale — safely)
        for (int right = 0; right < s.length(); right++) {
            top = Math.max(top, ++counts[s.charAt(right) - 'A']);
            if (right - left + 1 - top > k) {
                counts[s.charAt(left) - 'A']--; // over budget: slide, don't shrink
                left++;
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

TIME O(N)SPACE O(26)JAVA · RACE PACE · 16 LN

class Solution {
    public int characterReplacement(String s, int k) {
        int best = 0;
        for (int start = 0; start < s.length(); start++) {
            int[] counts = new int[26];
            int top = 0;
            for (int end = start; end < s.length(); end++) {
                top = Math.max(top, ++counts[s.charAt(end) - 'A']);
                int length = end - start + 1;
                if (length - top <= k) {
                    best = Math.max(best, length);
                } else {
                    break; // the deficit only grows from here
                }
            }
        }
        return best;
    }
}

TIME O(N²)SPACE O(26)JAVA · TRAINING PACE · 19 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED