Longest Repeating Character Replacement | Leetcode 424

The problem “Longest Repeating Character Replacement” asks for the length of the longest substring that can be converted into a string of all the same character by replacing at most k characters. In other words, within any window, if the number of characters that are not the most frequent character is ≤ k, that window is valid.

This is a hallmark sliding window problem where the key insight is to track the most frequent character count in the current window, and ensure the window size minus this count is within the replacement budget k.

Here’s the [Problem Link] to begin with.

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.
There may exists other ways to achieve this answer too.

Constraints:

• 1 <= s.length <= 105
• s consists of only uppercase English letters.
• 0 <= k <= s.length

Brute Force (Check All Starts, Grow While Valid)

Intuition and Approach

• For each start index i, expand j and maintain a frequency map plus the max frequency in the current window.
• Compute the replacements needed: changes = (j - i + 1) - max_freq.
• If changes ≤ k, it’s valid; update answer; otherwise break (further expansion only increases changes).

This approach is intuitive and clean but remains O(n^2) in the worst case because for each i, we may scan many j.

Code

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        max_length = 0
        n = len(s)
        for i in range(0, n):
            hash_map = dict()
            max_freq = 0
            for j in range(i, n):
                hash_map[s[j]] = hash_map.get(s[j], 0) + 1
                max_freq = max(max_freq, hash_map[s[j]])
                changes = (j - i + 1) - max_freq
                if changes <= k:
                    max_length = max(max_length, j - i + 1)
                else:
                    break
        return max_length

Why It Works

• The max_freq character is treated as the “target” character to keep; the rest must be replaced.
• As soon as replacements exceed k, expanding further cannot help (window only grows), so break.

Complexity

• Time: O(n^2)
• Space: O(Σ) for frequency map (Σ is alphabet size, typically 26 for uppercase letters)

Better (Sliding Window with Recompute of max_freq Inside Shrink Loop)

Intuition and Approach

• Use a classic sliding window with two pointers (left, right).
• Expand right, update frequency map, and track max_freq.
• If the window becomes invalid (window_size - max_freq > k), shrink from the left.
• This version recomputes max_freq by scanning the frequency map during shrink, which is acceptable since Σ is small (e.g., uppercase A–Z).

Code

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        max_length = 0
        n = len(s)
        left = 0
        right = 0
        hash_map = dict()
        max_freq = 0
        while right < n:
            hash_map[s[right]] = hash_map.get(s[right], 0) + 1
            max_freq = max(max_freq, hash_map[s[right]])
            while right - left + 1 - max_freq > k:
                hash_map[s[left]] -= 1
                max_freq = 0
                for v in hash_map.values():
                    max_freq = max(max_freq, v)
                left += 1

            max_length = max(max_length, right - left + 1)
            right += 1
        return max_length

Why It Works

• The window is always adjusted to satisfy the validity criterion.
• Recomputing max_freq in the shrink loop keeps correctness even if the most frequent character count drops due to left moving.

Complexity

• Time: O(26·n) ≈ O(n) for uppercase English letters (or O(Σ·n) in general)
• Space: O(Σ)

Optimal (Sliding Window with Monotone max_freq Tracking)

Intuition and Approach

• Same sliding window, but we keep max_freq as a non-decreasing value as right expands.
• When shrinking from the left, we do NOT forcibly decrease max_freq. This is safe and a well-known trick: even if max_freq is slightly larger than the true current window max, the condition right - left + 1 - max_freq > k remains a correct filter (we might keep the window slightly larger, but we never overcount because we only use the condition to force shrinking, not to extend beyond validity).
• This ensures fully linear time with no recomputation.

Code

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        max_length = 0
        n = len(s)
        left = 0
        right = 0
        hash_map = dict()
        max_freq = 0
        while right < n:
            hash_map[s[right]] = hash_map.get(s[right], 0) + 1
            max_freq = max(max_freq, hash_map[s[right]])
            while right - left + 1 - max_freq > k:
                hash_map[s[left]] -= 1
                left += 1

            max_length = max(max_length, right - left + 1)
            right += 1
        return max_length

Why This Is Correct and Optimal

• The window condition relies on max_freq being an upper bound of the true max frequency in the window.
• Not reducing max_freq during shrink does not cause false acceptance; at worst, it causes extra shrinking later when needed.
• Each index moves at most once for right and at most once for left, ensuring O(n) time.

Complexity

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

Deep Dive: The Key Invariant

• Let window_size = right - left + 1 and max_freq = max count of any char in window.
• The number of replacements needed to make the window all the same char is window_size - max_freq.
• A window is valid iff window_size - max_freq ≤ k.
• The algorithm keeps the window maximal subject to this constraint; hence the longest seen window is the answer.

Common Pitfalls and Pro Tips

• Always compute changes = window_size - max_freq. If this exceeds k, shrink.
• In the optimal version, do not try to decrease max_freq during shrink; this can degrade performance without improving correctness.
• If the alphabet is known and small (e.g., uppercase), using a fixed-size array (size 26) instead of a dictionary is a micro-optimization.
• Works for any alphabet; just remember Σ impacts memory and the constants if you recompute.

When to Choose Which

• Use the Brute Force version only for learning or very small inputs.
• Use the Better version if recomputing max_freq is simpler for you and Σ is small – still effectively linear.
• Use the Optimal version for the cleanest O(n) performance without recomputation.

Summary

• Core idea: In any window, the minimum changes to make it uniform equals window_size - max_freq.
• Maintain a sliding window, track frequencies, and ensure window_size - max_freq ≤ k.
• The optimal approach with a non-decreasing max_freq achieves O(n) time and O(Σ) space – ideal for interviews and production.

This pattern, max window with a bounded number of changes based on the dominant character is extremely powerful and reappears in various string sliding window problems.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.