LeetCode 424: 가장 긴 반복 문자 교체 — 단계별 시각적 추적

Source: Dev.to

문제

k 번 이하의 문자 교체를 수행한 뒤 얻을 수 있는, 동일한 문자를 포함하는 가장 긴 부분 문자열의 길이를 찾으세요. 문자열의任意의 문자를 다른 대문자 영어 알파벳으로 교체할 수 있습니다.

접근법

슬라이딩 윈도우(두 포인터) 기법을 사용합니다.
윈도우 [left, right] 를 유지하면서, 교체가 필요한 문자 수가

(윈도우 크기) – (윈도우 내 가장 빈도가 높은 문자 개수)

가 k 를 초과하지 않도록 합니다.

• right 를 이동시키며 윈도우를 확장하고, 문자 빈도 맵을 업데이트합니다.
• 교체 필요 수가 k 를 초과하면 left 를 이동시켜 윈도우를 축소하고, 빈도 맵을 조정합니다.
• 지금까지 본 최대 윈도우 크기를 기록합니다; 이것이 정답이 됩니다.

복잡도

• 시간: O(n) – 각 문자를 최대 두 번씩 방문합니다.
• 공간: O(1) – 빈도 맵은 최대 26개의 대문자만 저장합니다.

참고 구현 (Python)

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

        while right  k:
                char_freq[s[left]] -= 1
                left += 1

            # update answer
            max_length = max(max_length, right - left + 1)
            right += 1

        return max_length

시각화

인터랙티브 시각화 열기 – TraceLit을 직접 사용해 보면서 모든 코드를 단계별로 따라가 보세요.