🟨 Longest Repeating Character Replacement (#424)

🔗 Problem Link

• LeetCode - Longest Repeating Character Replacement
• NeetCode - Longest Repeating Character Replacement

📋 Problem Statement

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.

💡 Examples

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 one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

🔑 Key Insights & Approach

Core Observation: In a valid window, window_length - max_frequency <= k. Use sliding window to maximize window size.

Why Sliding Window + Frequency Count?

• Track most frequent character in window
• If replacements needed (window_size - max_freq) > k, shrink window
• O(n) time complexity

Approaches:

1. Brute force all substrings: O(n²)
2. Sliding window with frequency count: O(26 * n) = O(n) - optimal

Pattern: "Sliding Window - Flexible Size" with character frequency tracking.

🐍 Solution: Python

Approach: Sliding Window with Frequency Map

Time Complexity: O(n) | Space Complexity: O(1) - only 26 letters

from collections import defaultdict

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = defaultdict(int)
        left = 0
        max_freq = 0
        max_length = 0

        for right in range(len(s)):
            # Add current character to window
            count[s[right]] += 1
            max_freq = max(max_freq, count[s[right]])

            # Check if window is valid
            # window_length - most_frequent_char_count <= k
            window_length = right - left + 1

            if window_length - max_freq > k:
                # Shrink window from left
                count[s[left]] -= 1
                left += 1

            # Update max length
            window_length = right - left + 1
            max_length = max(max_length, window_length)

        return max_length

Approach 2: Optimized (No Need to Recalculate max_freq)

Time Complexity: O(n) | Space Complexity: O(1)

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

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

            # If window invalid, slide both pointers
            if (right - left + 1) - max_freq > k:
                count[s[left]] -= 1
                left += 1

        return len(s) - left

🔵 Solution: Golang

Approach: Sliding Window

Time Complexity: O(n) | Space Complexity: O(1)

func characterReplacement(s string, k int) int {
    count := make(map[byte]int)
    left := 0
    maxFreq := 0
    maxLength := 0

    for right := 0; right < len(s); right++ {
        count[s[right]]++

        // Update max frequency
        if count[s[right]] > maxFreq {
            maxFreq = count[s[right]]
        }

        // Check if window is valid
        windowLength := right - left + 1
        if windowLength-maxFreq > k {
            count[s[left]]--
            left++
        }

        windowLength = right - left + 1
        if windowLength > maxLength {
            maxLength = windowLength
        }
    }

    return maxLength
}

📚 References

• NeetCode - Longest Repeating Character Replacement