LeetCode 424 - Longest Repeating Character Replacement

Given a string consisting of uppercase English letters and an integer k, this Medium problem asks for the maximum length of a substring containing the same letter after performing at most k character replacements. I solved this using a sliding window while tracking the frequency of the most common character (max_freq) seen within the window.

---

Problem link and explanation

• Problem: 424. Longest Repeating Character Replacement
• Summary: Given a string s and an integer k, return the length of the longest substring containing identical characters that can be formed by changing up to k characters.

For any window of length L, the minimum number of replacements needed to make all characters identical is L - max_freq, where max_freq is the count of the most frequent character in that window. The window remains valid as long as (right - left + 1) - max_freq <= k.

---

Approach

Advance the right boundary to expand the window, update the character frequency count, and refresh max_freq.

for right in range(len(s)):
    count[s[right]] = count.get(s[right], 0) + 1
    max_freq = max(max_freq, count[s[right]])

    while (right - left + 1) - max_freq > k:
        count[s[left]] -= 1
        left += 1

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

1. Window expansion: Add the incoming character s[right] to the frequency map and update max_freq = max(max_freq, count[s[right]]). Comparing only against the newly incremented character count avoids scanning the entire map on every step.
2. Window contraction: When the number of required replacements exceeds k, increment left and decrement count[s[left]] until the window is valid again.
3. Update maximum length: Track the largest valid window size (right - left + 1) encountered so far.

---

Complexity analysis

• Time complexity: O(n)
  • Both left and right pointers advance across the string in a single direction, so each character is processed at most twice.
• Space complexity: O(1)
  • The hash table stores at most 26 distinct uppercase English letters.

---

Implementation code

class Solution:

    def characterReplacement(self, s: str, k: int) -> int:
        count = {}
        max_freq = 0
        left = 0
        max_length = 0

        for right in range(len(s)):
            count[s[right]] = count.get(s[right], 0) + 1
            max_freq = max(max_freq, count[s[right]])

            while (right - left + 1) - max_freq > k:
                count[s[left]] -= 1
                left += 1

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

        return max_length

---

Summary and reflection

A critical efficiency insight is that max_freq does not need to decrease when shrinking the window. Because the goal is finding the global maximum window length, any smaller window with a lower max_freq cannot exceed the previously established maximum answer anyway. This eliminates the need to recalculate maximum frequencies across the map during shrink operations.