Longest Repeating Character Replacement

Problem

Given a string of uppercase letters and an integer k, return the length of the longest substring you can make all-equal by replacing at most k characters.

Constraints

• 1 ≤ s.length ≤ 10⁵
• 0 ≤ k ≤ s.length
• uppercase English

Approach — Sliding Window

This is a Sliding Window problem. The idea: keep a moving window over the sequence, expanding and shrinking it while tracking the answer in a single pass. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time.

Solution code

Python

class Solution:
    def characterReplacement(self, s, k):
        from collections import Counter
        count = Counter()
        left = best = maxf = 0
        for right, c in enumerate(s):
            count[c] += 1
            maxf = max(maxf, count[c])
            while (right - left + 1) - maxf > k:
                count[s[left]] -= 1
                left += 1
            best = max(best, right - left + 1)
        return best

Java

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

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.