[LeetCode] 424. Longest Repeating Character Replacement

🔦 문제 링크

🔊 파이썬 알고리즘 인터뷰 책을 참고했습니다.

• 문제

영어 대문자로만 구성된 문자열이 주어지면 해당 문자열에 대해 최대 k 개의 연산을 수행 할 수 있습니다. 한 번의 작업에서 문자열의 문자를 선택하고 다른 대문자 영어 문자로 변경할 수 있습니다. 위의 작업을 수행 한 후 얻을 수 있는 모든 반복 문자를 포함하는 가장 긴 하위 문자열의 길이를 찾습니다.

✍️ 풀이

---

슬라이딩 윈도우를 늘려가는 동시에 조건에 따라 줄여가며 검사를 수행한다.

1. 슬라이딩 윈도우는 항상 오른쪽으로 한 칸씩 이동한다.
2. 현재 슬라이딩 윈도우에 들어있는 값들의 수를 계산한다.
3. 슬라이딩 윈도우의 크기 - 가장 큰 비중의 값의 갯수 = 바꿔야하는 갯수이다.
4. 만약, 바꿔야하는 갯수가 k보다 크다면 현재 슬라이딩 윈도우는 불가하므로 왼쪽을 증가시켜 슬라이딩 윈도우의 크기를 줄인다.
5. k가 크거나 같다면 현재 윈도우와 최대 윈도우의 크기를 비교해 최대 윈도우를 갱신시킨다.

🛠 코드

---

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        left = right = 0
        max_len = 0
        count = collections.Counter()
        for right in range(1, len(s) + 1):
            count[s[right - 1]] += 1
            
            # left부터 right까지 문자들 중 가장 많은 비중을 차지 하는 문자의 개수 ==> most
            most = count.most_common(1)[0][1]
            # 우리는 most 기준으로 나머지 문자들을 most문자로 바꿀 계획이다.
            remain = right - left - most # 따라서 리메인(남은 문자)의 수가 바꿔야하는 수의 갯수라고 볼 수 있다.
            
            # 바꿔야 할 문자가 바꿀 수 있는 문자 수보다 많을 때 -> left를 증가시켜 윈도우크기를 줄인다.
            if remain > k: 
                count[s[left]] -= 1
                left += 1
            max_len = max(right - left, max_len)

        return max_len
        

---

📝 정리

---

🎈 참고

---

Book 링크