Skip to content

047 — Longest Repeating Character Replacement

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 2 revisions

47 — Longest Repeating Character Replacement

LeetCode 424 · Medium. Given a string s consisting of uppercase English letters and an integer k, you can replace up to k characters in s with any other uppercase letter. Return the length of the longest substring you can make consist of a single repeating character after at most k replacements.

🍽️ Intuition

Picture a row of colored tiles and a small budget of k "repaint tokens." You want the longest stretch of tiles you could make all one color by spending at most k tokens repainting the odd ones out. The cheapest way to unify a stretch is to keep whichever color is already the majority inside that stretch, and only repaint the minority tiles — so the number of repaints a window needs is just (window length) - (count of its most common color). As long as that number is ≤ k, the window is achievable; the moment it exceeds k, the window needs more repaints than you can afford, and it has to shrink.

🚩 Pattern-Recognition Cue

"Longest substring... after replacing at most k characters" is a contiguous + optimize signal with a numeric budget constraint standing in for the usual "no repeats" or "at most K distinct" rule — the window is valid exactly while windowLength - mostFrequentCharCount <= k. Whenever a sliding window's validity check involves a running frequency count and a budget for how many "wrong" elements are tolerated, that's this same shape.

🐢 Brute Force

For every starting index, extend the substring one character at a time, tracking a frequency count and the running max frequency, and check the replacement budget at every length.

func characterReplacementBruteForce(_ s: String, _ k: Int) -> Int {
    let chars = Array(s)
    let n = chars.count
    var best = 0

    for i in 0..<n {
        var counts: [Character: Int] = [:]
        var maxFreq = 0
        for j in i..<n {
            counts[chars[j], default: 0] += 1
            maxFreq = max(maxFreq, counts[chars[j]]!)

            let windowLength = j - i + 1
            if windowLength - maxFreq <= k {
                best = max(best, windowLength)
            }
        }
    }

    return best
}

Big-O: O(n²) time — every starting index rescans forward to the end. O(1) extra space (the alphabet is a fixed 26 letters, so counts never grows unbounded).

🚀 Optimal

Slide a two-pointer window across the string, keeping a 26-slot frequency count and the highest frequency seen inside the current window. Shrink from the left only when the window can no longer be unified within the replacement budget.

func characterReplacement(_ s: String, _ k: Int) -> Int {
    let chars = Array(s)
    var counts = [Int](repeating: 0, count: 26)
    let aVal = Character("A").asciiValue!

    var left = 0
    var maxFreq = 0
    var best = 0

    for right in 0..<chars.count {
        let rIndex = Int(chars[right].asciiValue! - aVal)
        counts[rIndex] += 1
        maxFreq = max(maxFreq, counts[rIndex])

        let windowLength = right - left + 1
        if windowLength - maxFreq > k {
            let lIndex = Int(chars[left].asciiValue! - aVal)
            counts[lIndex] -= 1
            left += 1
        }

        best = max(best, right - left + 1)
    }

    return best
}

// smoke test
print(characterReplacement("ABAB", 2))     // 4
print(characterReplacement("AABABBA", 1))  // 4

Big-O: O(n) time — one forward pass, with left advancing at most once per step. O(1) extra space — a fixed 26-slot count array.

🔑 The Key Insight

The brute force recomputes the frequency table and max frequency from scratch for every starting index. The optimal solution slides the window instead of restarting it, but the subtle trick is that maxFreq is never decremented even after the window shrinks — it's allowed to go stale. That's safe because maxFreq is only ever used to test whether the window can grow past its current best length; a stale (too-high) maxFreq can only make that test harder to fail, never cause an invalid window to be wrongly accepted as a new best. Once the true best has already been recorded, an incorrect stale value simply can't produce a length that beats it, so there's no need to pay for a full rescan to keep maxFreq perfectly accurate at every step — this is what keeps the whole scan at O(n).

🔗 Related Chapters

  • Sliding Window — the expand/contract skeleton, with a budget-based validity check instead of a strict "no repeats" one.
  • Arrays & Strings — the string being scanned.
  • Hash Maps & Hash Sets — the character-frequency count that drives the window's validity, here specialized to a fixed 26-slot array instead of a dictionary.

🧸 Memory Sentence

Longest Repeating Character Replacement is a row of tiles and a repaint budget — keep whichever color already dominates the window, and shrink only when repainting the rest would cost more tokens than you have.

✅ Check Your Understanding

maxFreq in the optimal solution is never decreased, even when the window shrinks and its true highest frequency has actually dropped. Explain why this "staleness" can never cause the algorithm to report a best value that's too large — that is, why an artificially inflated maxFreq can never make an actually-invalid window get counted as valid at a new best length.

⬅️ Previous: Longest Substring Without Repeating Characters · Next: Permutation in String ➡️

Clone this wiki locally