Longest Repeating Character Replacement

Examples

Input: s = "ABAB", k = 2
Output: 4

Change both "B"s to "A" (or both "A"s to "B") to get "AAAA" or "BBBB", length 4.

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

Change the one "B" inside "ABAB" (positions 1-4, "ABAB") to get "AAAA", giving a substring of length 4. The final "A" can't be joined without another change.

Input: s = "AAAA", k = 0
Output: 4

No changes needed or allowed — the whole string is already one repeated letter.

Constraints

• 1 <= s.length <= 10^5

• s consists of only uppercase English letters.

• 0 <= k <= s.length

Approach

The brute-force way is to check every substring, and for each one count how many characters differ from its most frequent letter — that count is exactly how many replacements it would take. If that count is at most k, the substring is achievable, so track the longest one you find. That means re-counting letter frequencies for overlapping substrings again and again.

A sliding window does much better. Grow a window from left to right, keeping a running count of how often each letter appears inside it. A window of length L needs L - (count of its most frequent letter) replacements to become a single repeated letter, since every character other than the most common one has to change. As long as that number is <= k, the window is valid, so let it keep growing. The moment it isn't valid, shrink from the left by one. The window's length only ever grows or holds steady as it slides — it can be shown that it never needs to shrink below the best length already found, so tracking the maximum window length seen is enough to get the right answer.

Solutions

Brute Force — Check Every Substring

For every substring, count how many characters are not the most frequent letter in it — that's the number of replacements needed — and check it against k.

function characterReplacement(s, k) {
  let best = 0;

  for (let start = 0; start < s.length; start++) {
    const counts = {};
    let maxCount = 0;

    for (let end = start; end < s.length; end++) {
      counts[s[end]] = (counts[s[end]] || 0) + 1;
      maxCount = Math.max(maxCount, counts[s[end]]);

      const length = end - start + 1;
      const replacementsNeeded = length - maxCount;

      if (replacementsNeeded <= k) {
        best = Math.max(best, length);
      }
    }
  }

  return best;
}

Time: O(n²) · Space: O(26) — constant, one count per letter

Optimal — Sliding Window with Max Frequency

Grow the window while tracking letter counts and the highest frequency seen in it. If the window ever needs more than k replacements, shrink it from the left by one. The window's size only ever grows over the whole scan, so its final size is the answer.

function characterReplacement(s, k) {
  const counts = {};
  let left = 0;
  let maxCount = 0;
  let best = 0;

  for (let right = 0; right < s.length; right++) {
    counts[s[right]] = (counts[s[right]] || 0) + 1;
    maxCount = Math.max(maxCount, counts[s[right]]);

    const windowLength = right - left + 1;
    if (windowLength - maxCount > k) {
      counts[s[left]]--;
      left++;
    }

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

  return best;
}

Time: O(n) · Space: O(26) — constant, one count per uppercase letter