[파이썬 알고리즘 인터뷰][슬라이딩윈도우] 가장 긴 반복 문자 대체

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

문자열 s에 대해 k개를 변경하여 만들 수 있는 가장 긴 반복문자열의 길이 출력

 

책에서 구현된 코드

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        left = right = 0
        counts = collections.Counter()
        for right in range(1, len(s) + 1):
            counts[s[right - 1]] += 1
            # 가장 흔하게 등장하는 문자 탐색
            max_char_n = counts.most_common(1)[0][1]

            # k 초과시 왼쪽 포인터 이동
            if right - left - max_char_n > k:
                counts[s[left]] -= 1
                left += 1
        return right - left

 

기억해야할 기법

• 문제 접근 방식
  
  • 문제 범위를 윈도우로 축소
  • 윈도우 내에서 바꿔야할 문자의 개수 = 윈도우의 길이 - 윈도우 내에서 빈도수가 가장 높은 문자의 수
  • k개 이상을 바꿔야할 경우 윈도우를 길이를 축소(윈도우를 이동)

 

내가 구현한 코드

None

• 책에 구현된 알고리즘이 복잡한 문제에 비해 매우 깔끔한 코드라고 생각한다
• 다른 방식으로 풀어보고 싶었는데 못풀겠다
• 슬라이딩 윈도우 문제가 매우 재미있다 찾아서 풀어야겠다!