Longest Repeating Character Replacement

Difficulty: Medium

Problem

You have a string s of capital letters and a budget of k edits, where each edit turns one character into any other letter. Using at most k edits, find how long a run of one repeated letter you can create inside s, and return that length.

Example

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Changing the B at index 2 into an A makes the run "AAAA" at indexes 0 to 3, length 4. Changing the A at index 3 into a B would make the run "BBBB" at indexes 2 to 5 instead, which is equally long.

Brute-force approach

Try every possible substring, and for each one: count frequencies, find max frequency, calculate replacements needed, and if replacements ≤ k, update the answer.

Steps

  1. For each starting position i (outer loop)
  2. For each ending position j ≥ i (inner loop)
  3. Count frequency of each character in substring[i..j]
  4. Find max frequency in current window
  5. Calculate: replacements = length - maxFreq
  6. If replacements ≤ k, update maxLen

Time complexity: O(n²) · Space complexity: O(1)

Trade-offs

  • Checking every possible substring is O(n²)
  • Too slow for large inputs
  • Sliding window is much better → O(n)

Optimal approach

Key insight: A window is valid if: window length - top count <= k. That is the number of edits it needs. We do not care which letter we convert to: we always convert everything to the most common one.

Use a window that takes in one letter at a time on the right. When it is too long, it drops its oldest letter on the left, so it slides and keeps its length.

Steps

  1. Take in the next letter on the right, add it to the count map
  2. Update maxCount = max(maxCount, count[current letter]); never lower it
  3. Check: (window length - maxCount) > k?
  4. If yes, slide: remove the left letter and move left++
  5. Update best = max(best, window length)

Time complexity: O(n) · Space complexity: O(1)

Pseudocode

function characterReplacement(s, k):
    count = empty map; left = 0; maxCount = 0; best = 0
    for right from 0 to n-1:
        count[s[right]]++
        maxCount = max(maxCount, count[s[right]])
        if (right - left + 1) - maxCount > k:
            count[s[left]]--; left++
        best = max(best, right - left + 1)
    return best

Hints

  • Window is valid if (window size - most frequent char count) <= k
  • Use a window that slides: when it is too long, drop the left letter and keep the length
  • Track maxCount, the biggest count of one letter in any window so far, and never lower it

Complexity questions

Time to check all substrings?

O(n²). O(n²) substrings, O(26) work each = O(n²)

Time for sliding window?

O(n). Each position visited once by left and right = O(n)

Space for frequency count?

O(1). Fixed 26 letters = O(1) space

What makes a window valid?

Window size - top count <= k. Window is valid when (length - top count) <= k

Check your understanding of Longest Repeating Character Replacement

What operation is allowed?

Replace up to k characters. You can replace at most k characters to make a valid substring.

Given 'AABABBA' and k=1, what's the longest valid substring?

4. Change the B at index 2 to get 'AAAA' (length 4).

Related problems

Keep practising