View in English →

Code › algorithm-study

LeetCode 424 - Longest Repeating Character Replacement

최다 빈도 문자를 추적하는 슬라이딩 윈도우로 최대 연속 부분 문자열 길이를 구하는 Python 풀이

algorithmleetcodesliding-windowhash-tablestringpythonlearning

대문자 알파벳으로 이루어진 문자열에서 최대 k개의 문자를 다른 문자로 바꾸었을 때, 동일한 문자로만 채울 수 있는 가장 긴 연속 부분 문자열의 길이를 구하는 Medium 문제다. 현재 윈도우 내에서 가장 많이 등장한 문자의 빈도수(max_freq)를 추적하며 유효한 슬라이딩 윈도우 크기를 유지했다.

문제 링크 & 설명

  • 문제 링크: 424. Longest Repeating Character Replacement
  • 요약: 문자열 s와 정수 k가 주어졌을 때, 임의의 문자를 최대 k번 다른 알파벳으로 변경하여 만들 수 있는 가장 긴 동일 문자 연속 부분 문자열의 길이를 반환한다.

현재 윈도우 구간의 길이가 L이고, 그 안에서 가장 많이 등장한 문자의 빈도가 max_freq라면 나머지 문자들의 개수는 L - max_freq이다. 이 변경해야 할 문자 수가 k 이하((right - left + 1) - max_freq <= k)일 때만 해당 윈도우는 유효하다.

접근 방법

오른쪽 포인터를 전진시키며 해시맵에 문자 수를 기록하고, 새롭게 추가된 문자로 max_freq를 갱신한다.

for right in range(len(s)):
    count[s[right]] = count.get(s[right], 0) + 1
    max_freq = max(max_freq, count[s[right]])

    while (right - left + 1) - max_freq > k:
        count[s[left]] -= 1
        left += 1

    max_length = max(max_length, right - left + 1)
  1. 윈도우 확장: right 포인터가 가리키는 문자를 카운트 맵에 반영하고, max_freq = max(max_freq, count[s[right]])로 현재까지 확인된 최다 빈도를 즉시 갱신한다. 매번 맵 전체를 돌며 최댓값을 찾을 필요 없이 새로 들어온 문자의 빈도만 비교하면 충분하다.
  2. 윈도우 축소: 변경해야 하는 문자의 수가 k를 초과하면 유효한 상태가 될 때까지 left 포인터를 오른쪽으로 이동하며 왼쪽 문자의 카운트를 뺀다.
  3. 최댓값 갱신: 조건을 만족하는 유효한 구간의 길이 (right - left + 1)로 max_length를 갱신한다.

복잡도 분석

  • 시간 복잡도: O(n)
    • 두 포인터 left, right는 문자열의 처음부터 끝까지 한 방향으로만 전진하므로 각 문자는 최대 두 번만 처리된다.
  • 공간 복잡도: O(1)
    • 입력 문자열이 영문 대문자로만 구성되어 있어 해시 테이블에 저장되는 엔트리는 최대 26개로 고정된다.

구현 코드

class Solution:

    def characterReplacement(self, s: str, k: int) -> int:
        count = {}
        max_freq = 0
        left = 0
        max_length = 0

        for right in range(len(s)):
            count[s[right]] = count.get(s[right], 0) + 1
            max_freq = max(max_freq, count[s[right]])

            while (right - left + 1) - max_freq > k:
                count[s[left]] -= 1
                left += 1

            max_length = max(max_length, right - left + 1)

        return max_length

요약 및 회고

이 풀이의 핵심은 슬라이딩 윈도우 내에서 윈도우가 줄어들 때 max_freq를 굳이 다시 줄이지 않아도 정답에 영향을 주지 않는다는 점이다. 우리의 목표는 ‘최대’ 윈도우 길이를 찾는 것이므로, 이전에 달성한 max_freq보다 더 큰 빈도가 나타나지 않는 한 기존 최대 길이 기록은 갱신되지 않는다. 덕분에 루프마다 맵 전체의 최댓값을 다시 계산하는 비효율을 없애고 선형 시간에 깔끔하게 문제를 해결할 수 있다.