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 to 'B' resulting in "BBABBA".

Steps and Explanation

The core idea is to use a sliding window approach. We maintain a window within the string and track the frequency of each character within that window. The key insight is that the length of the longest substring with the same character (after replacements) is limited by the size of the window.

We use a dictionary char_freq to store the frequency of each character in the current window. max_freq keeps track of the maximum frequency of any character within the window. The condition for expanding the window is window_length - max_freq <= k. This means we can still perform replacements to make all characters in the window the same.

If the condition is violated, we shrink the window from the left by decrementing left. We also update char_freq accordingly. We continue this process until the condition is met again, or the window is shrunk to size 0.

The algorithm iterates through the string, expanding and shrinking the window as needed, keeping track of the maximum window length encountered.

Code

from collections import defaultdict

def characterReplacement(s, k):
    """
    Finds the length of the longest substring containing the same letter after at most k replacements.

    Args:
        s: The input string.
        k: The maximum number of replacements allowed.

    Returns:
        The length of the longest substring.
    """

    left = 0
    max_length = 0
    char_freq = defaultdict(int)

    for right, char in enumerate(s):
        char_freq[char] += 1
        max_freq = max(char_freq.values())
        window_length = right - left + 1

        while window_length - max_freq > k:
            char_freq[s[left]] -= 1
            left += 1
            window_length -= 1
            max_freq = max(char_freq.values())

        max_length = max(max_length, window_length)

    return max_length

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 char_freq dictionary uses constant space (at most 26 entries for uppercase English characters).