Longest Repeating Character Replacement

Why it belongs on this sheet

This is a great medium because the window condition is not obvious at first, but once you see it, the problem becomes very clean.

Pattern

Window size minus best frequency

Approach

Keep counts for characters in the current window and track the highest frequency ever seen in the window. If window size - max frequency > k, shrink from the left.

Java solution

class Solution {
  public int characterReplacement(String s, int k) {
    int[] count = new int[26];
    int left = 0;
    int maxFrequency = 0;
    int best = 0;

    for (int right = 0; right < s.length(); right++) {
      int index = s.charAt(right) - 'A';
      count[index]++;
      maxFrequency = Math.max(maxFrequency, count[index]);

      while ((right - left + 1) - maxFrequency > k) {
        count[s.charAt(left) - 'A']--;
        left++;
      }

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

    return best;
  }
}

Complexity

• Time: O(n)
• Space: O(1)

Interview note

The slightly stale maxFrequency is still safe here. That is the key insight to explain.