Longest Repeating Character Replacement

medium string sliding window

Problem

You are given a string s and an integer k. You can change any character in s to any other uppercase English letter at most k times. Return the length of the longest substring containing the same letter you can obtain.

A window is valid when (window length) − (frequency of the most common letter inside it) ≤ k, because that difference is the number of replacements you would need. Slide right; whenever the window becomes invalid, slide left forward.

Inputs = "AABABBA", k = 1

Output4

Replace the middle 'B' or the second 'A' to get a run of 4 identical letters.

s (letters)

def character_replacement(s, k):
    count = {}
    left = 0
    max_freq = 0
    best = 0
    for right in range(len(s)):
        count[s[right]] = count.get(s[right], 0) + 1
        max_freq = max(max_freq, count[s[right]])
        while (right - left + 1) - max_freq > k:
            count[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

function characterReplacement(s, k) {
  const count = {};
  let left = 0, maxFreq = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    count[s[right]] = (count[s[right]] || 0) + 1;
    maxFreq = Math.max(maxFreq, count[s[right]]);
    while ((right - left + 1) - maxFreq > k) {
      count[s[left]]--;
      left++;
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

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

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

Explanation

We want the longest window that can become all one letter using at most k changes. The clever insight is that a window is valid exactly when (window length) − (count of its most frequent letter) ≤ k, because that difference is how many letters we'd have to replace.

So we slide a window with a right pointer and keep a count map of how many of each letter are inside. We also track maxFreq, the highest single-letter count seen. Whenever the window needs more than k replacements, we move left forward and shrink it.

A neat detail: we never bother lowering maxFreq when shrinking. That is fine because the answer only grows when we find a window with a higher max frequency, so a slightly stale maxFreq never produces a wrong larger answer.

Example: s = "AABABBA", k = 1. As the window covers AABA, the most common letter is A (3 of 4), so only 1 replacement is needed — valid, length 4. That length 4 ends up being the answer.

Each character is added once and removed at most once, so the whole thing runs in linear time.

Time: O(n) Space: O(1) (alphabet fixed)