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 the end with 'B' to get "AABBBB".

Steps

1. Sliding Window Approach: We use a sliding window to iterate through the string.
2. Frequency Count: Maintain a frequency map (charCount) to track the count of each character within the current window.
3. Max Frequency: Keep track of the maximum frequency (maxFreq) of any character in the current window.
4. Window Size and k: The length of the valid window is determined by the relationship between the window size (windowSize), maxFreq, and k. A window is valid if windowSize - maxFreq <= k. This means that we can replace at most k characters to make all characters in the window the same.
5. Expand and Contract: If the window is valid, expand the window by moving the right pointer. If the window is invalid, contract the window by moving the left pointer.
6. Update Maximum Length: Keep track of the maximum valid window size (maxLength).

Explanation

The algorithm leverages the sliding window technique to efficiently find the longest substring. The core idea is that we only need to consider the frequency of the most frequent character within a window. If the number of characters that need to be replaced (windowSize - maxFreq) is less than or equal to k, the window is valid. The algorithm systematically expands and contracts the window to find the largest valid window size.

Code

function characterReplacement(s: string, k: number): number {
    let left = 0;
    let maxFreq = 0;
    let maxLength = 0;
    const charCount = new Map<string, number>();

    for (let right = 0; right < s.length; right++) {
        const char = s[right];
        charCount.set(char, (charCount.get(char) || 0) + 1);
        maxFreq = Math.max(maxFreq, charCount.get(char)!);

        while (right - left + 1 - maxFreq > k) {
            const leftChar = s[left];
            charCount.set(leftChar, charCount.get(leftChar)! - 1);
            left++;
        }
        maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
};

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 with the left pointer).
• Space Complexity: O(1). The charCount map uses at most 26 entries (for uppercase English characters), resulting in constant space complexity.