LeetCode [424]: Longest Repeating Character Replacement

📌 LeetCode [424]: Longest Repeating Character Replacement

🔗 문제 링크

---

문제 설명 📄

문자열 s와 정수 k가 주어졌습니다.
k번까지 문자를 변경할 수 있을 때, 동일한 문자를 포함하는 가장 긴 부분 문자열의 길이를 반환해야 합니다.

• 변경은 문자열 s의 어떤 문자를 선택하여 다른 대문자 영어 알파벳으로 교체하는 작업입니다.

---

문제 접근 방식 📋

1. 슬라이딩 윈도우 활용:
   • 문자열의 두 포인터 l과 r을 사용해 윈도우를 확장하거나 축소합니다.
   • 부분 문자열 길이와 문자 빈도를 유지하면서 조건을 만족하도록 윈도우를 조정합니다.
2. 조건 확인:
   • 윈도우 내에서 최빈 문자 외의 문자 개수가 k를 초과하면 윈도우의 왼쪽 포인터(l)를 이동시킵니다.
3. 최적화:
   • 최빈 문자 개수(max_freq)를 슬라이딩 윈도우 내에서 유지하여, 전체 문자 빈도를 다시 계산하지 않도록 최적화합니다.

---

Solution 💻

첫 번째 코드

from collections import Counter

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        counts = Counter()
        l = 0
        max_len = 0

        for r in range(len(s)):
            counts[s[r]] += 1 

            max_freq = max(counts.values())

            if (r - l + 1) - max_freq > k:
                counts[s[l]] -= 1
                l += 1

            max_len = max(max_len, r - l + 1)

        return max_len

시간 복잡도 ⏲️

• 오른쪽 포인터 r가 문자열 s의 길이만큼 이동: (O(n)).
• 매번 max(counts.values())를 호출: 최악의 경우 (O(n \times 26)) ((n)은 문자열 길이, 26은 알파벳 수).
• 전체 시간 복잡도: (O(n \times 26) = O(n)).

공간 복잡도 🗄️

• 문자 빈도를 저장하는 counts: (O(26)).

---

리팩토링 🛠️

개선된 코드

from collections import Counter

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        counts = Counter()
        l = 0
        max_len = 0
        max_freq = 0

        for r in range(len(s)):
            counts[s[r]] += 1
            max_freq = max(max_freq, counts[s[r]])

            if (r - l + 1) - max_freq > k:
                counts[s[l]] -= 1
                l += 1

            max_len = max(max_len, r - l + 1)

        return max_len

리팩토링 후 시간 복잡도 ⏲️

• max_freq를 매번 갱신하므로 (O(1)) 상수 시간에 수행.
• 오른쪽 포인터 r가 문자열 s를 (O(n))만큼 순회.
• 최종 시간 복잡도는 (O(n)).

리팩토링 후 공간 복잡도 🗄️

• 문자 빈도를 저장하는 counts: (O(26)).

---

리팩토링 코드의 장점 🌟

• max(counts.values())를 매번 계산하지 않고, max_freq를 유지하므로 효율성 향상.
• (O(n)) 시간 복잡도로 최적화.