18. Longest Repeating Character Replacement · DSA Practice

s has uppercase letters. You may change at most k characters to any other uppercase letter. Return the length of the longest substring that can be made of one repeated letter.

Example 1

Input: s = "AABABBA", k = 1

Output: 4

Example 2

Input: s = "ABAB", k = 2

Output: 4

Hint 1

A window is valid when (window length − count of its most frequent letter) ≤ k.

Sliding WindowString

Approach 1: Try every letter

For each of 26 letters run a window counting the other letters.

⏱ Time O(26 · n)💾 Space O(1)

Approach 2: Single window ✅

Track the top frequency; shrink when the window needs more than k changes. top never needs to decrease.

⏱ Time O(n)💾 Space O(1)

Reference solution for Single window (time O(n), space O(1)). Each solution passes every test in all four languages.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = defaultdict(int)
        left = top = best = 0
        for right, ch in enumerate(s):
            count[ch] += 1
            top = max(top, count[ch])                 # most common letter in the window
            while (right - left + 1) - top > k:       # too many letters to change
                count[s[left]] -= 1
                left += 1
            best = max(best, right - left + 1)
        return best

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

class Solution {
public:
    int characterReplacement(string s, int k) {
        int count[26] = {0}, left = 0, top = 0, best = 0;
        for (int right = 0; right < (int)s.size(); right++) {
            top = max(top, ++count[s[right] - 'A']);
            while (right - left + 1 - top > k) count[s[left++] - 'A']--;
            best = max(best, right - left + 1);
        }
        return best;
    }
};

function characterReplacement(s, k) {
  const count = new Array(26).fill(0);
  let left = 0, top = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    top = Math.max(top, ++count[s.charCodeAt(right) - 65]);
    while (right - left + 1 - top > k) count[s.charCodeAt(left++) - 65]--;
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Sliding Window.