424. Longest Repeating Character Replacement

Problem Description

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.

Constraints:

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

Python Solution

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        # Initialize window pointers and character count
        left = 0
        count = {}
        max_count = 0
        max_length = 0
        
        # Slide the window
        for right in range(len(s)):
            # Add the right character to count
            count[s[right]] = count.get(s[right], 0) + 1
            max_count = max(max_count, count[s[right]])
            
            # If window is invalid, shrink it
            window_size = right - left + 1
            if window_size - max_count > k:
                count[s[left]] -= 1
                left += 1
            
            # Update max length
            max_length = max(max_length, right - left + 1)
        
        return max_length

Java Solution

class Solution {
    public int characterReplacement(String s, int k) {
        // Initialize window pointers and character count
        int left = 0;
        int[] count = new int[26];
        int maxCount = 0;
        int maxLength = 0;
        
        // Slide the window
        for (int right = 0; right < s.length(); right++) {
            // Add the right character to count
            count[s.charAt(right) - 'A']++;
            maxCount = Math.max(maxCount, count[s.charAt(right) - 'A']);
            
            // If window is invalid, shrink it
            int windowSize = right - left + 1;
            if (windowSize - maxCount > k) {
                count[s.charAt(left) - 'A']--;
                left++;
            }
            
            // Update max length
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
}

C++ Solution

class Solution {
public:
    int characterReplacement(string s, int k) {
        // Initialize window pointers and character count
        int left = 0;
        vector count(26, 0);
        int maxCount = 0;
        int maxLength = 0;
        
        // Slide the window
        for (int right = 0; right < s.length(); right++) {
            // Add the right character to count
            count[s[right] - 'A']++;
            maxCount = max(maxCount, count[s[right] - 'A']);
            
            // If window is invalid, shrink it
            int windowSize = right - left + 1;
            if (windowSize - maxCount > k) {
                count[s[left] - 'A']--;
                left++;
            }
            
            // Update max length
            maxLength = max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
};

JavaScript Solution

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var characterReplacement = function(s, k) {
    // Initialize window pointers and character count
    let left = 0;
    const count = new Map();
    let maxCount = 0;
    let maxLength = 0;
    
    // Slide the window
    for (let right = 0; right < s.length; right++) {
        // Add the right character to count
        count.set(s[right], (count.get(s[right]) || 0) + 1);
        maxCount = Math.max(maxCount, count.get(s[right]));
        
        // If window is invalid, shrink it
        const windowSize = right - left + 1;
        if (windowSize - maxCount > k) {
            count.set(s[left], count.get(s[left]) - 1);
            left++;
        }
        
        // Update max length
        maxLength = Math.max(maxLength, right - left + 1);
    }
    
    return maxLength;
};

C# Solution

public class Solution {
    public int CharacterReplacement(string s, int k) {
        // Initialize window pointers and character count
        int left = 0;
        int[] count = new int[26];
        int maxCount = 0;
        int maxLength = 0;
        
        // Slide the window
        for (int right = 0; right < s.Length; right++) {
            // Add the right character to count
            count[s[right] - 'A']++;
            maxCount = Math.Max(maxCount, count[s[right] - 'A']);
            
            // If window is invalid, shrink it
            int windowSize = right - left + 1;
            if (windowSize - maxCount > k) {
                count[s[left] - 'A']--;
                left++;
            }
            
            // Update max length
            maxLength = Math.Max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
}