Leetcode # 424. Longest Repeating Character Replacement

2023.08.04
★★ Medium LeetCode Sliding Window

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

Solution: Sliding Window

Time Complexity: O(len(s))
Space Complexity: O(len(s))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def characterReplacement(self, s: str, k: int) -> int:
    pos = collections.defaultdict(list)
    for i, c in enumerate(s):
      pos[c].append(i)
    
    ans = min(1 + k, len(s))
    for c in pos:
      left = curr = 0
      rest_k = k

      for right in range(1, len(pos[c])):
        # do logic here to add arr[right] to curr
        rest_k -= pos[c][right] - pos[c][right - 1] - 1

        while rest_k < 0:
          # remove arr[left] from curr
          left += 1
          rest_k += pos[c][left] - pos[c][left - 1] - 1

        # update ans
        
        ans = max(ans, min(pos[c][right] - pos[c][left] + 1 + rest_k, len(s)))
        print(c, ans, pos[c][left], pos[c][right], rest_k)
    
    return ans

More Refined Solution

max_frequency	:=	max([s[start, end].count(c) for c in set(s[start, end])])
not_valid	:=	Current sliding window is valid or not
	=	(end – start + 1) – max_frequency > k
	=	len(Current sliding window) – max_frequency > k
	=	len([c for c in s if c != c_{max_frequency}]) > k (s[start, end].count(c_{max_frequency}) == max_frequency)

Time Complexity: O(len(s))
Space Complexity: O(26) = O(1) (26 lowercase letters)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def characterReplacement(self, s: str, k: int) -> int:
    start = 0
    frequency_map = collections.Counter()
    max_frequency = 0
    longest_substring_length = 0
    for end in range(len(s)):
      frequency_map[s[end]] += 1
      max_frequency = max(max_frequency, frequency_map[s[end]])

      not_valid = (end - start + 1) - max_frequency > k
      if not_valid:
        frequency_map[s[start]] -= 1
        start += 1

      longest_substring_length = end - start + 1 

    return longest_substring_length

Last Updated on 2023/08/16 by A1go