Longest Repeating Character Replacement

Difficulty: Medium

Problem

Given a string s and an integer k, you can replace at most k characters to make a substring with all the same character. Return the length of the longest such substring.

Example

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace one B at index 4 with A to get "AAAA" (or replace A at index 3 to get "BBBB").

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)