424. Longest Repeating Character Replacement#

Difficulty: Medium

Link to Problem: To see the Longest Repeating Character Replacement problem on LeetCode, click here!

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.

Constraints:

  • 1 <= s.length <= 105

  • s consists of only uppercase English letters.

  • 0 <= k <= s.length

def characterReplacement(s, k):
    max_length = 0  # Initialize the maximum length
    max_count = 0   # Initialize the maximum count of repeating characters
    start = 0       # Initialize the start of the sliding window
    char_count = {} # Dictionary to store the count of each character

    for end in range(len(s)):
        # Update the count of the current character in the dictionary
        char_count[s[end]] = char_count.get(s[end], 0) + 1
        
        # Update the maximum count of repeating characters
        max_count = max(max_count, char_count[s[end]])
        
        # Check if the current window size is greater than k
        if (end - start + 1) - max_count > k:
            # Move the start of the window to the right
            char_count[s[start]] -= 1
            start += 1
        
        # Update the maximum length
        max_length = max(max_length, end - start + 1)

    return max_length

Explanation:#

  1. We initialize some variables:

    • max_length to keep track of the maximum length of the substring containing the same letter.

    • max_count to keep track of the maximum count of repeating characters within the current window.

    • start to represent the start index of the sliding window.

    • char_count is a dictionary that will store the count of each character within the current window.

  2. We use a for loop to iterate through the characters of the string s.

  3. Inside the loop, we do the following for each character at position end:

    • Update the count of the current character in the char_count dictionary.

    • Update the max_count to be the maximum of the current max_count and the count of the current character. This keeps track of the maximum count of repeating characters within the current window.

  4. We check if the current window size (the difference between end and start plus one) minus the max_count is greater than k. This condition checks whether we have exceeded the allowed number of replacements (k) within the current window.

    • If we have exceeded the allowed replacements, it means we need to shrink the window from the left side. We do this by moving the start of the window to the right and decrementing the count of the character at s[start] in the char_count dictionary. This effectively removes characters from the left side of the window until we have a valid window again.

    • By doing this, we ensure that the difference between the current window size and the max_count is always less than or equal to k.

  5. After each character, we update the max_length to be the maximum of the current max_length and the size of the current window (end - start + 1).

  6. Finally, we return max_length, which holds the length of the longest substring containing the same letter with at most k replacements.

Test cases#

# Example 1:
s1 = "ABAB"
k1 = 2
print(characterReplacement(s1, k1))

4

# Example 2:
s2 = "AABABBA"
k2 = 1
print(characterReplacement(s2, k2))

4

Let’s analyze the time and space complexity of the provided code:

Time Complexity:

  • The code uses a single for loop to iterate through the characters of the input string s. The loop runs from the beginning to the end of the string.

  • Inside the loop, we perform constant-time operations such as updating the char_count dictionary and updating variables like max_count and max_length.

  • The code’s time complexity is primarily determined by the loop, which iterates through each character in the string once. Therefore, the time complexity is O(n), where n is the length of the input string s.

Space Complexity:

  • The code uses several variables to store information, but the space they consume is constant and does not depend on the size of the input string. These variables include max_length, max_count, start, and char_count. Therefore, the space complexity is O(1) or constant space.

In summary, the time complexity of the code is O(n), where n is the length of the input string, and the space complexity is O(1), as it uses a constant amount of additional space regardless of the input size. This algorithm efficiently solves the problem with a linear time complexity.

Challenging Exercises:#

  1. Optimization Challenge: Modify the code to find the longest substring containing the same letter with at most k replacements in O(n) time complexity and O(1) space complexity. Hint: You may need to update the approach to achieve this.

  2. Variation with Lowercase Letters: Extend the problem to include both uppercase and lowercase English letters in the input string s. Write a function that can handle this extended input and still find the longest substring with at most k replacements efficiently.