[코테] 리트코드 슬라이딩 윈도우 424. Longest Repeating Character Replacement

424. Longest Repeating Character Replacement

문제 링크

https://leetcode.com/problems/longest-repeating-character-replacement/description/

문제 설명

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

제한 사항

• 1 <= s.length <= 10^5
• s consists of only uppercase English letters.
• 0 <= k <= s.length

입출력 예 #1

1. Input : s = “ABAB”, k = 2
2. Output : 4
3. Explanation : Replace the two ‘A’s with two ‘B’s or vice versa.

입출력 예 #2

1. Input : s = “AABABBA”, k = 1
2. Output : 4
3. Explanation : Replace the one ‘A’ in the middle with ‘B’ and form “AABBBBA”. The substring “BBBB” has the longest repeating letters, which is 4. There may exists other ways to achieve this answer too.

문제 풀이

투 포인터, 슬라이딩 윈도우, counter를 모두 이용한 풀이

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        left = right = 0
        counts = collections.Counter()

        for right in range(1, len(s) + 1):
            counts[s[right - 1]] += 1
            # 가장 흔하게 등장하는 문자 탐색
            max_char_n = counts.most_common(1)[0][1]

            # k 초과시 왼쪽 포인터 이동
            if right - left - max_char_n > k :
                counts[s[left]] -= 1
                left += 1
        return right - left