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 index 3 to 'B', the longest substring is "BBBB".

Steps

The problem can be solved using a sliding window approach. We maintain a window of characters and count the frequency of each character within the window. The key idea is to track the maximum frequency of any character within the window. If the length of the window minus the maximum frequency (which represents the number of characters that need to be replaced) exceeds k, we shrink the window from the left. Otherwise, we expand the window to the right.

Explanation

1. Initialization: We initialize a map (or unordered_map) to store the frequency of each character within the sliding window, two pointers left and right to define the window boundaries (both initially at 0), a variable maxFreq to track the maximum frequency within the window, and a variable maxLength to store the maximum length of the substring found so far.

2. Sliding Window: The right pointer iterates through the string. For each character, we increment its frequency in the map. We also update maxFreq to be the maximum frequency seen so far within the window.

3. Window Size Check: We check if the current window size (right - left + 1) minus maxFreq is greater than k. This condition means we have more characters that need replacement than allowed (k). If this is true, we shrink the window from the left by decrementing the frequency of the character at left and incrementing left. We also re-calculate maxFreq.

4. Update Maximum Length: If the condition in step 3 is false, it means the current window is valid (we can replace at most k characters to make all characters the same). We update maxLength with the current window size (right - left + 1).

5. Iteration: We continue steps 2-4 until the right pointer reaches the end of the string.

6. Return: Finally, we return maxLength.

Code

#include <iostream>
#include <string>
#include <map>

using namespace std;

int characterReplacement(string s, int k) {
    map<char, int> charCount;
    int left = 0;
    int right = 0;
    int maxFreq = 0;
    int maxLength = 0;

    while (right < s.length()) {
        charCount[s[right]]++;
        maxFreq = max(maxFreq, charCount[s[right]]);

        if (right - left + 1 - maxFreq > k) {
            charCount[s[left]]--;
            left++;
        }
        maxLength = max(maxLength, right - left + 1);
        right++;
    }
    return maxLength;
}

int main() {
    string s1 = "ABAB";
    int k1 = 2;
    cout << "Longest substring length for '" << s1 << "' with k = " << k1 << ": " << characterReplacement(s1, k1) << endl; // Output: 4

    string s2 = "AABABBA";
    int k2 = 1;
    cout << "Longest substring length for '" << s2 << "' with k = " << k2 << ": " << characterReplacement(s2, k2) << endl; // Output: 4

    return 0;
}

Complexity

• Time Complexity: O(N), where N is the length of the string. We iterate through the string at most twice (once with the right pointer and once implicitly when shrinking the window).
• Space Complexity: O(1). The charCount map stores at most 26 entries (for uppercase English characters), so the space used is constant.