[DSA][Sliding Window] 02. Longest Repeating Character Replacement

LeetCode 424

 

02. Longest Repeating Character Replacement

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.

 

 

[질문하기]

- 문자열은 26개의 대문자 Character로만 이루어지고 그 안에서만 교체할 수 있나요? YES

 

 

[아이디어]

- 바꿔야 할 문자 수 = 현재 윈도우 길이 - 가장 많이 등장한 문자 수

 

 

[풀이 1] Sliding Window

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        countMap = {}
        res, L, maxFreq = 0, 0, 0

        for R in range(len(s)):
            countMap[s[R]] = 1 + countMap.get(s[R], 0)
            maxFreq = max(maxFreq, countMap[s[R]])

            while (R - L + 1) - maxFreq > k:
                countMap[s[L]] -= 1
                L += 1
            res = max(res, R - L + 1)
        
        return res

처음 이 문제를 접하면 요구사항이 어렵게 느껴지지만, 사실 문제의 핵심 키워드는 "containing the same letter"이다.

우리가 최종적으로 구하고자하는 것은 최대 K개의 문자를 바꿔서 동일한 문자로만 이루어진 가장 긴 Substring이다.

여기서 중요한 것은 어떤 문자들을 바꾸는지가 아니라, 어떤 문자로 바꿀 것인지이다. 왜냐하면 주어진 substring 내에서 가장 많이 등장하는 문자를 기준으로 삼고, 그 외의 문자들을 모두 바꾸면 최소 횟수로 원하는 substring을 만들 수 있기 때문이다.

 

이를 효율적으로 구현하기 위해 Sliding window로 Substring을 만들고 각 문자의 빈도를 해시맵으로 관리할 수 있다. window의 길이에서 max_freq를 빼면 바꿔야 할 문자열의 개수를 알 수 있고, 이 값이 k보다 작거나 같으면 윈도우를 오른쪽으로 확장하고, 초과하면 왼쪽을 한 칸씩 옮기며 크기를 조정한다.

 

⏱️ 시간복잡도

문자열을 한 번 순회하기 때문에 O(n)의 시간 복잡도를 갖는다.

🧠 공간복잡도

최악의 경우 모든 char를 저장해야 하므로 unique character의 개수를 m이라 하면 O(m)의 공간 복잡도를 갖는다.