Problem statement

You are given a string s and an integer k. You may change at most k characters to any other uppercase letter. Return the length of the longest substring containing one repeated letter you can obtain.

Example 1

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace both A's (or both B's).

Example 2

Input: s = "AABABBA", k = 1
Output: 4

Constraints

• 1 <= s.length <= 40
• s consists of lowercase English letters.
• 0 <= k <= s.length

Hints for Longest Repeating Character Replacement

1. Hint 1

   A window is valid when (window length - count of its most frequent letter) <= k.

2. Hint 2

   Grow the right edge; shrink from the left only when the window turns invalid.

How to solve Longest Repeating Character Replacement

A window can be made uniform with at most k replacements exactly when the number of characters that are not the window's most frequent one is at most k — that is, windowLength - maxFrequency <= k. Slide a window maintaining that invariant and take the largest.

Approach

1. Keep a frequency table for the characters inside the window and a left edge l.
2. Extend the right edge, incrementing the incoming character's count.
3. While windowLength - maxFrequency exceeds k, advance l, decrementing the outgoing character's count.
4. Record the window length once the invariant is restored.
5. The largest such length is the answer.

Why it works

Keeping the most frequent character and replacing everything else is always the cheapest way to make a window uniform — any other choice needs at least as many replacements. So windowLength - maxFrequency is exactly the minimum cost for that window, and comparing it against k is an exact feasibility test. The window only shrinks to restore feasibility, so for each right edge it is as long as it can be.

Complexity

• Time — O(n · alphabet)
• Space — O(1)

Pitfalls

• The cost is windowLength - maxFrequency, not the count of any particular character.
• Measure the window only after restoring the invariant.
• Decrement the outgoing character's count as the left edge moves, or the frequencies drift.
• k = 0 is legal and reduces to the longest run of a single repeated character.

Reference solution

Python

def characterReplacement(s: str, k: int) -> int:
    count = [0] * 26
    start = 0
    max_freq = 0
    best = 0
    for i, ch in enumerate(s):
        ci = ord(ch) - 97
        count[ci] += 1
        max_freq = max(max_freq, count[ci])
        while i - start + 1 - max_freq > k:
            count[ord(s[start]) - 97] -= 1
            start += 1
        best = max(best, i - start + 1)
    return best

Java

public static int characterReplacement(String s, int k) {
    int[] count = new int[128];
    int l = 0, best = 0;
    for (int r = 0; r < s.length(); r++) {
        count[s.charAt(r)]++;
        while (true) {
            int maxc = 0;
            for (int c = 0; c < 128; c++) if (count[c] > maxc) maxc = count[c];
            if (r - l + 1 - maxc <= k) break;
            count[s.charAt(l)]--;
            l++;
        }
        if (r - l + 1 > best) best = r - l + 1;
    }
    return best;
}

C++

int characterReplacement(string s, int k) {
    vector<int> count(128, 0);
    int l = 0, best = 0;
    for (int r = 0; r < (int) s.size(); r++) {
        count[(unsigned char) s[r]]++;
        while (true) {
            int maxc = 0;
            for (int c = 0; c < 128; c++) if (count[c] > maxc) maxc = count[c];
            if (r - l + 1 - maxc <= k) break;
            count[(unsigned char) s[l]]--;
            l++;
        }
        if (r - l + 1 > best) best = r - l + 1;
    }
    return best;
}

JavaScript

var characterReplacement = function(s, k) {
    const count = new Array(26).fill(0);
    let start = 0, maxFreq = 0, best = 0;
    for (let i = 0; i < s.length; i++) {
        const ci = s.charCodeAt(i) - 97;
        count[ci]++;
        maxFreq = Math.max(maxFreq, count[ci]);
        while (i - start + 1 - maxFreq > k) {
            count[s.charCodeAt(start) - 97]--;
            start++;
        }
        best = Math.max(best, i - start + 1);
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design a Food Rating System Medium
• Design Bitset Medium
• Iterator for Combination Medium
• Time Based Key-Value Store Medium
• Map Sum Pairs Medium
• Implement Magic Dictionary Medium