Longest Repeating Character Replacement medium

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.

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' at index 0 or 6 to 'B', and the substring "BBBB" is obtained.

Steps and Explanation

The problem can be efficiently solved using a sliding window approach. We maintain a window within the string and keep track of the frequency of each character within that window. The core idea is: As long as the number of replacements needed (which is the window size minus the frequency of the most frequent character) is less than or equal to k, we can extend the window. If it exceeds k, we shrink the window from the left until the condition is met again.

Here's a breakdown of the algorithm:

1. Initialization: Create a map charCount to store the frequency of each character in the current window, and initialize left and maxLen to 0. maxFreq keeps track of the maximum frequency of any character in the current window.

2. Sliding Window: Iterate through the string using right as the right boundary of the window. For each character:

   • Increment its frequency in charCount.
   • Update maxFreq to be the maximum frequency seen so far in the window.
   • Check if right - left + 1 - maxFreq (replacements needed) is less than or equal to k. If true, the window is valid; otherwise, it needs to be shrunk.

3. Window Shrinking: While the window is invalid, decrement the frequency of the character at left in charCount, move left to the right, and recompute maxFreq. This process continues until the window becomes valid again.

4. Update maxLen: After each valid window expansion, update maxLen to the maximum length seen so far.

5. Return maxLen: After iterating through the entire string, return the maxLen.

Code (Java)

class Solution {
    public int characterReplacement(String s, int k) {
        Map<Character, Integer> charCount = new HashMap<>();
        int left = 0;
        int maxFreq = 0;
        int maxLen = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);
            maxFreq = Math.max(maxFreq, charCount.get(c));

            while (right - left + 1 - maxFreq > k) {
                char leftChar = s.charAt(left);
                charCount.put(leftChar, charCount.get(leftChar) - 1);
                left++;
                maxFreq = 0; //recompute maxFreq after shrinking.
                for(int freq : charCount.values()){
                    maxFreq = Math.max(maxFreq, freq);
                }
            }
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

Complexity

• Time Complexity: O(N), where N is the length of the string. We iterate through the string at most twice (once for expanding the window and at most once for shrinking it).
• Space Complexity: O(1). The charCount map uses constant space because it only stores the frequency of uppercase English characters (26 characters at most).