424. Longest Repeating Character Replacement

Problem Statement

link: LeetCode.cn LeetCode

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:

Input: s = "ABAB", k = 2 Output: 4

Input: s = "AABABBA", k = 1 Output: 4

Solution Approach

The solution utilizes a sliding window approach to find the longest substring containing the same letter, allowing at most k replacements.

Algorithm

1. Initialize two pointers, left and right, to define a window.
2. Move the right pointer to expand the window while keeping track of the count of characters within the window. If the number of characters to be replaced exceeds k, move the left pointer to shrink the window.
3. Update the maximum length of the substring with the same letter as the window expands, and return the maximum length once the window reaches the end of the string.

Implement

    class Solution:
      def minOperations(self, nums: List[int], x: int) -> int:
          n = len(s)
          left, right = 0, 0
          res = 0
          counter = collections.Counter()
          while right < n:
              counter[s[right]] += 1
              while right - left + 1 - counter.most_common(1)[0][1] > k:
                  counter[s[left]] -= 1
                  left += 1
              res = max(res, right - left + 1)
              right += 1
          return res
       
     

    
    

Twitter  facebook  Email