Longest repeating character replacement

Problem Link

Longest Repeating Character Replacement – LeetCode #424

Problem Statement

You are given a string s consisting only of uppercase English letters, and an integer k.

You can choose at most k characters in the string and replace them with any other uppercase letter.

Your task is to return the length of the longest possible substring containing the same character, after at most k replacements.

Examples

• Input: s = "ABAB", k = 2
  Output: 4
  Explanation: Replace the two 'A's or two 'B's → make "BBBB" or "AAAA".

• Input: s = "AABABBA", k = 1
  Output: 4
  Explanation: Replace one 'A' with 'B' → get "AABBBBA" → "BBBB" has length 4.

Constraints

• 1 <= s.length <= 10⁵

• s contains only uppercase English letters (A–Z)

• 0 <= k <= s.length

Intuition

This is a variable size sliding window problem with a condition:

We want the longest window [l...r] where we can make all characters equal by changing at most k characters.

Instead of checking each possible character to change to, we keep track of the most frequent character inside the current window.

The key insight is:

For a window of size r - l + 1, we can make all characters equal if
(r - l + 1) - maxFreq ≤ k

Why?

• maxFreq is the count of the most frequent character in the window.

• The remaining characters are what we must replace, and if that count is ≤ k, we can make the window valid.

Approach

1. Use a frequency array (int[128]) to track character counts in the window.

2. Use two pointers: l (left) and r (right).

3. At each step:

   • Include s[r] in the window and update its frequency.

   • Track the maxFreq of any character in the current window.

   • If the number of characters to replace (window size - maxFreq) exceeds k, shrink the window from the left (l++).

   • Update the maxLen with the current window size.

Java Code

class Solution {
    public int characterReplacement(String s, int k) {
        int[] freq = new int[128];
        int maxFreq = 0, maxLen = 0, l = 0;

        for (int r = 0; r < s.length(); r++) {
            freq[s.charAt(r)]++;
            maxFreq = Math.max(maxFreq, freq[s.charAt(r)]);

            // If more than k replacements needed, shrink the window
            while ((r - l + 1) - maxFreq > k) {
                freq[s.charAt(l)]--;
                l++;
            }

            maxLen = Math.max(maxLen, r - l + 1);
        }

        return maxLen;
    }
}

Time and Space Complexity

• Time Complexity: O(n)
  Each character is processed at most twice (once added, once removed from window)

• Space Complexity: O(1)
  Fixed-size array of size 128 (ASCII)

Dry Run

Input:

s = "AABABBA", k = 1

Steps:

• Initialize: l = 0, r = 0, maxFreq = 0, maxLen = 0

• Expand window:

  • "A" → freq = 1, maxFreq = 1 → valid

  • "AA" → freq = 2, maxFreq = 2 → valid

  • "AAB" → freq['B'] = 1, maxFreq = 2 → window size = 3 → need 1 replacement → valid

  • "AABA" → freq['A'] = 3 → valid

  • "AABAB" → maxFreq = 3, size = 5 → 2 replacements → invalid → shrink

  • Final max length found: 4

Output: 4

Conclusion

This problem is a variable size sliding window with frequency tracking, where:

• You optimize the window based on a condition involving a count (characters to replace).

• You don't need to recalculate maxFreq after shrinking the window — it's a useful optimization:

  • The algorithm still works because overestimating maxFreq only delays shrinking, which is acceptable.

Pattern Recognition

This problem falls under the Sliding Window → Variable Size with Frequency Map category:

• Related problems:

  • Longest substring with at most k distinct characters

  • Longest substring without repeating characters

  • Longest substring with character replacement