리트코드 424번 Longest Repeating Character Replacement (python)

Problem

LeetCode - The World's Leading Online Programming Learning Platform

Solution

풀이 1

from collections import Counter

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        left = right = 0
        counter = Counter()

        for right, char in enumerate(s, 1):
            counter[char] += 1
            max_char_n = counter.most_common(1)[0][1]

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

        return right - left

left와 right 사이에 있는 문자들의 개수 중 가장 많은 것 이외의 문자가 k개 이상이라면 left도 같이 옮긴다. 즉, window의 크기가 연속된 문자가 많이 나올수록 늘어날 뿐 줄어들지 않는다. 탐색이 모두 끝났을 때의 창문의 크기가 최대 길이이다.

Reference

파이썬 알고리즘 인터뷰 77번