424. Longest Repeating Character Replacement ★★★★★

424. Longest Repeating Character Replacement

 

https://youtu.be/gqXU1UyA8pk

 

이 문제는 슬라이딩 윈도우 [Sliding Window Variable Size]  + 해시맵을 활용해서 풀 수 있어요.
핵심은 윈도우 안의 가장 많이 나온 문자를 기준으로
나머지를 바꾸는 데 k번 이하로 가능한지 체크하는 것입니다.

---

✅ 아이디어 요약:

• 윈도우 내 가장 많이 나온 문자 수 = max_count
• 현재 윈도우 크기 = r - l + 1
• 바꿔야 하는 문자 수 = 전체 윈도우 크기 - max_count
• 이 값이 k보다 작거나 같을 때만 윈도우 유지, 아니면 왼쪽 포인터 이동

---

✅ 코드 (주석 포함)

from collections import defaultdict

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        l = 0
        max_count = 0  # 윈도우 안에서 가장 자주 등장하는 문자 수
        count = defaultdict(int)  # 각 문자의 등장 횟수 저장
        max_len = 0

        for r in range(len(s)):
            count[s[r]] += 1
            max_count = max(max_count, count[s[r]])  # 윈도우 내 최빈 문자 수 업데이트

            # (윈도우 크기 - 최빈 문자 수) > k → 교체 범위 초과 → 왼쪽 이동
            while (r - l + 1) - max_count > k:
                count[s[l]] -= 1  # 왼쪽 문자 제거
                l += 1  # 왼쪽 포인터 오른쪽으로 이동

            max_len = max(max_len, r - l + 1)  # 현재 윈도우 길이로 최대값 갱신

        return max_len

---

🔍 예제 분석

예제 1: s = "XYYX", k = 2

• 'XYYX' 전체를 'XXXX' 또는 'YYYY'로 만들 수 있음 → 정답: 4

예제 2: s = "AAABABB", k = 1

• 'AABAB' 구간에서, 하나의 B를 A로 바꾸면 'AAAAA' → 길이 5 → 정답: 5

---

⏱️ 시간복잡도

• O(n) – 슬라이딩 윈도우 내에서 각 문자는 최대 한 번씩 왼쪽으로 나가므로 전체는 선형 시간

최종 코드

from collections import defaultdict

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        # k 번 바꿀 수 있음
        charCount = defaultdict(int)  # 각 문자의 등장 횟수를 저장할 딕셔너리

        l_idx = 0                     # 슬라이딩 윈도우의 왼쪽 포인터
        longest = 0                  # 조건을 만족하는 가장 긴 부분 문자열의 길이 저장
        maxCount = 0                 # 현재 윈도우 내에서 가장 많이 등장한 문자 개수 (=최빈 문자)

        for r_idx in range(len(s)):  # 오른쪽 포인터를 0부터 끝까지 이동시키며 윈도우 확장
            charCount[s[r_idx]] += 1  # 현재 문자의 개수 +1
            maxCount = max(maxCount, charCount[s[r_idx]])  # 최빈 문자 수 갱신

            # 윈도우 전체 길이 > 최빈 문자 수 + k → 바꿔도 안 됨 → 윈도우 줄이기
            while maxCount + k < (r_idx - l_idx + 1):  # 윈도우 사이즈가 maxCount + k보다 크면
                # 지금 left 글자를 없애야 하니, 우선 charCount 에서는 줄이고
                charCount[s[l_idx]] -= 1

                # maxCount = max(maxCount, charCount[s[l_idx]])
                # → 이건 사실 필요 없음 (최대값이 줄어들 수 있기 때문, 다시 계산해야 정확)
                # 하지만 실제 정답에는 영향을 거의 안 줌
                # → 정확하려면 윈도우 내부에서 maxCount를 다시 계산해야 함
                # 다만, 매번 계산하면 시간 복잡도가 올라가므로 최대값 유지 방식이 더 효율적

                l_idx += 1  # 다음 단어로 이동, l_idx 증가

            # 현재 윈도우의 길이와 비교해서 최대 길이 갱신
            longest = max(longest, r_idx - l_idx + 1)

        return longest

 

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        # 최대 k 번 교체 가능
        # return 최장 부분수열(반복되는 문자)의 길이
        
        # 문자의 개수 counting -> dict 사용
        chCount = defaultdict(int)
        longest = 0
        maxCount = 0 # 최대 문자 수
        left =0

        for right in range(len(s)):
            chCount[s[right]] +=1
            maxCount = max(maxCount, chCount[s[right]])

            # 윈도우 크기 > 가장긴글자수 + k번교체 이면,
            # 같게 만들기 위해서, left를 증가시켜서 윈도우를 작게..
            while (right-left+1) > maxCount + k:
                # left 증가하기 전에, 우선 chCount 에서 해당 글자 제거 후.
                chCount[s[left]] -=1
                # maxCount 도 다시 갱신
                maxCount = max(maxCount, chCount[s[left]])
                # left 증가
                left +=1
            longest = max(longest, right-left+1)
                

        return longest