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 with 'B', or replace the one 'A' at index 5 with 'B'.

Steps and Explanation

The problem can be efficiently solved using a sliding window approach. The core idea is to maintain a window within the string and track the frequency of each character within that window. We expand the window as long as the number of replacements needed (k) is less than or equal to the allowed replacements (k). When the number of replacements exceeds k, we shrink the window from the left, removing characters until the condition is satisfied.

1. Initialization: We initialize a maxLen variable to store the maximum length of the substring and a charFreq dictionary to store the frequency of each character in the current window. We also initialize left and right pointers to mark the window boundaries (both starting at 0).

2. Sliding Window: The right pointer iterates through the string. For each character encountered:

   • Increment its frequency in charFreq.
   • Find the maximum frequency (maxFreq) within the current window.
   • Calculate the number of replacements needed (replacements) which is the window size minus the maximum frequency.

3. Window Adjustment: If replacements is less than or equal to k, it means we can still accommodate the current character within the allowed replacements. We extend the window by incrementing right. Otherwise, we need to shrink the window from the left. We decrement the frequency of the leftmost character and move the left pointer to the right.

4. Update Max Length: After each window adjustment, we update maxLen with the maximum length seen so far (which is right - left + 1).

5. Return Result: Once the right pointer reaches the end of the string, we return maxLen.

Code

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int CharacterReplacement(string s, int k) {
        if (string.IsNullOrEmpty(s)) return 0;

        int left = 0;
        int right = 0;
        int maxLen = 0;
        Dictionary<char, int> charFreq = new Dictionary<char, int>();

        while (right < s.Length) {
            charFreq[s[right]] = charFreq.GetValueOrDefault(s[right], 0) + 1;
            int maxFreq = charFreq.Values.Max();
            int replacements = (right - left + 1) - maxFreq;

            if (replacements <= k) {
                maxLen = Math.Max(maxLen, right - left + 1);
                right++;
            } else {
                charFreq[s[left]]--;
                left++;
            }
        }

        return maxLen;
    }
}

Complexity

• Time Complexity: O(N), where N is the length of the string. We iterate through the string at most twice (once with right and once implicitly with left).
• Space Complexity: O(1). The charFreq dictionary uses constant space because it only stores frequencies of uppercase English characters (at most 26).