LeetCode 424. Longest Repeating Character Replacement

파이썬 알고리즘 인터뷰 77번(리트코드 424번) Longest Repeating Character Replacement
https://leetcode.com/problems/longest-repeating-character-replacement/

나의 풀이

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        if not s:
            return 0

        result = 0
        left = right = 0
        char_count = collections.defaultdict(int)
        char_max = set()
        char_max_count = 0
        change = 0
        char_sum = 0

        while right < len(s):
            while change <= k and right < len(s):
                char_count[s[right]] += 1
                if char_count[s[right]] == char_max_count:
                    char_max.add(s[right])
                elif char_count[s[right]] > char_max_count:
                    char_max.clear()
                    char_max.add(s[right])
                    char_max_count = char_count[s[right]]
                change = (right - left + 1) - char_max_count
                if change <= k:
                    result = max(result, right - left + 1)
                right  += 1
            right -= 1
            
            char_count[s[left]] -= 1
            if s[left] in char_max:
                if len(char_max) == 1:
                    char_max_count -= 1
                else:
                    char_max.remove(s[left])
            left += 1
            if left > right:
                return result
            char_count[s[right]] -= 1
            change = (right - left + 1) - char_max_count
        
        return result

• 핵심 아이디어인 right, left 사의 거리에서 가장 많이 나온 문자의 수를 뺀 값이 k가 된다. 는 잘 파악했는데 자꾸 여러 엣지 케이스들을 처리하다가 코드가 너무 복잡해졌다.
• 이전의 두 문제는 hard이고 이게 medium인데 이게 더 어려운 것 같다.

다른 풀이1

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        left = right = 0
        max_char_n = 0
        counts = collections.defaultdict(int)
        for right in range(1, len(s) + 1):
            counts[s[right - 1]] += 1
            max_char_n = max(max_char_n, counts[s[right - 1]])

            if right - left - max_char_n > k:
                counts[s[left]] -= 1
                left += 1
        
        return right - left

• 같은 아이디어인데 훨씬… 깔끔하게 작성할 수 있다. 왜 이렇게 하지 못했던거지.
• 내가 이렇게 풀지 못했던 이유는 아래 배운 점에 정리

배운 점

• 먼저, k개 보다 많은 수정이 필요해서 left를 오른쪽으로 밀어줄 때는 가장 많이 출현한 횟수를 업데이트할 필요가 없다. 또한 가장 많이 출현한 문자의 출현 횟수만 트래킹하면 된다. 나는 가장 많이 출현한 문자를 트래킹하려고 했었다. 그러다 보니 가장 많이 출현한 문자가 여러 개일 때 다양한 엣지 케이스가 등장했다. 이를 수습하다가 코드가 산으로 갔다.
• 다음으로, k개 보다 많은 수정이 필요해서 left를 오른쪽으로 한 칸 밀어줄 때, right를 한 칸 밀어주면 되는데, 이때 조건을 만족하지 않아도 된다. 조건을 만족하지 않아도 윈도우를 줄일 필요는 없다. 우리는 윈도우의 최댓값을 찾는 것이기 때문이다. 또한 right, left 의 값을 찾는 것이 아니라 그 차만 중요하다.