[Neetcode 150/Sliding Window] Longest Repeating Character Replacement

https://neetcode.io/problems/longest-repeating-substring-with-replacement

NeetCode

🛠 해결 방법

1. 슬라이딩 윈도우를 사용하여 left와 right 두 개의 포인터로 윈도우 크기를 조정한다.
2. 윈도우 내에서 가장 많이 등장한 문자를 찾고, 나머지 문자들을 k번 변경할 수 있는지 확인한다.
3. 윈도우 크기에서 가장 많이 등장한 문자 개수를 제외한 나머지 문자가 k보다 크면 left 포인터를 이동하여 윈도우를 줄인다.
4. 최대 윈도우 크기를 갱신하면서 탐색을 진행한다.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        left = 0
        max_count = 0  # 현재 윈도우에서 가장 많이 등장한 문자 개수
        max_length = 0
        char_count = Counter()  # 윈도우 내 문자 개수 저장

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

            # (윈도우 크기 - 가장 많이 등장한 문자 개수) > k 이면 left 이동
            if (right - left + 1) - max_count > k:
                char_count[s[left]] -= 1
                left += 1  # 윈도우 크기 줄이기

            # 최대 길이 갱신
            max_length = max(max_length, right - left + 1)

        return max_length

💡 코드 설명

1. char_count를 사용하여 현재 윈도우 내 문자의 개수를 저장한다.
2. max_count는 윈도우 내에서 가장 많이 등장한 문자 개수를 유지한다.
3. (윈도우 크기 - max_count) > k 조건을 만족하면 left 포인터를 이동시켜 윈도우 크기를 조정한다.
   • Case 1
     • s =(AAABA)AAAA
     • s = (AAAAAA)AAA -> 이런 경우에 right 포인터를 계속 증가시킬 수 있음
     • s = (AAAAAAAA)A -> 이런 경우에 right 포인터를 계속 증가시킬 수 있음
     • ...
   • Case 2
     • s = AAABABCAA
     • s = (AAABA)BCAA k = 1 -> 0 (이제 바꿀 수 있는 문자 개수가 0개 남았다는 뜻)
     • s =(AAAAAB)CAA 
     • s = (AAAAAB)CAA -> 더 이상 연속된 문자열 만드는 게 불가능. 따라서 left 포인터를 1 증가시킨다.
     • s = A(AAAAB)CAA -> k = 1 -> 0
     • s = A(AAAAA)CAA
     • s = A(AAAAAC)AA -> k = 0. C를 A로 바꾸는 게 불가능. 따라서 left 포인터를 1 증가시킨다.
     • s = AA(AAAB)CAA
4. 최댓값을 max_length에 저장하면서 결과를 구한다.

---

📌 시간 복잡도 분석

• 각 문자는 최대 한 번씩만 left와 right에 의해 이동
  → O(N)
• Counter 사용은 O(1) 연산이므로 성능에 큰 영향을 주지 않음.