LeetCode #424: Longest Repeating Character Replacement

LeetCode Solutions

https://leetcode.com/problems/longest-repeating-character-replacement/description/

To solve this problem in Python 3, we can use a sliding window approach that involves maintaining a count of the characters in the current window and expanding the window until the number of characters that need to be replaced is greater than k.

Here are the steps to follow:

  1. Initialize two pointers, left and right, to the start of the string.
  2. Initialize a dictionary, count, to store the count of each character in the current window.
  3. Initialize the max_len variable to 0.
  4. Iterate through the string using the right pointer and add each character to the count dictionary. If the number of characters that need to be replaced is greater than k, remove the leftmost character from the count dictionary and increment the left pointer until the number of characters that need to be replaced is less than or equal to k.
  5. Update the max_len variable with the length of the current substring.
  6. Return the max_len.

Here’s the Python 3 code that implements this approach:

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        left = right = 0
        count = {}
        max_len = 0
        for right in range(len(s)):
            count[s[right]] = count.get(s[right], 0) + 1
            while right - left + 1 - max(count.values()) > k:
                count[s[left]] -= 1
                left += 1
            max_len = max(max_len, right - left + 1)
        return max_len

In this code, we initialize the left and right pointers to the start of the string, the count dictionary to an empty dictionary, and the max_len variable to 0. We then iterate through the string using the right pointer and add each character to the count dictionary. If the number of characters that need to be replaced is greater than k, we remove the leftmost character from the count dictionary and increment the left pointer until the number of characters that need to be replaced is less than or equal to k. We then update the max_len variable with the length of the current substring and return it.

Time and Space Complexity:

The time complexity of this solution is O(n), where n is the length of the string s. This is because we only iterate through the string once.

The space complexity of this solution is O(1), because we are using constant space to store the left and right pointers, the count dictionary, and the max_len variable, regardless of the size of the string s.