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 4 into an A yields the run "AAAA" at the front, length 4. Flipping the A at index 3 into a B would give "BBBB" 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 - max_frequency_in_window <= k. We don't care which character we convert to - we always assume we convert everything to the most frequent character.

Use a sliding window that expands from the right and shrinks from the left only when invalid.

Steps

  1. Expand right, add character to frequency map
  2. Update maxFreq = max(maxFreq, count[current char])
  3. Check validity: (windowSize - maxFreq) > k?
  4. If invalid, shrink left: remove left char, move left++
  5. Update maxLength = max(maxLength, windowSize)

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

Pseudocode

function characterReplacement(s, k):
    count = frequency map
    left = 0
    maxFreq = 0
    maxLength = 0
    
    for right from 0 to n-1:
        count[s[right]]++
        maxFreq = max(maxFreq, count[s[right]])
        
        // window size - max freq = chars to replace
        while (right - left + 1) - maxFreq > k:
            count[s[left]]--
            left++
        
        maxLength = max(maxLength, right - left + 1)
    
    return maxLength

Hints

  • Window is valid if (window size - most frequent char count) <= k
  • Use sliding window with frequency count
  • Track the max frequency character in current window

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 - maxFreq <= k. Window is valid when (length - maxFreq) <= 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. Replace one B to get 'AAAA' (length 4).

Related problems

Keep practising