Logo

Longest Repeating Character Replacement

LeetCode의 424번째 문제인 Longest Repeating Character Replacement를 함께 풀어보도록 하겠습니다.

문제

문자열이 주어졌을 때 반복되는 글자를 포함하지 않는 가장 긴 부분 문자열(substring)의 길이를 구하라.

당신은 문자열 s와 정수 k가 주어집니다. 당신은 문자열에서 글자 하나를 골라서 다른 영어 대문자 바꿀 수 있으며, 이 작업을 최대 k번 수행할 수 있습니다.

이러한 작업들을 수행하여 얻을 수 있는 동일한 글자로 이루어진 가장 긴 부분 문자열의 길이를 반환하시오.

  • 1 <= s.length <= 105
  • s에는 영어 대문자만 들어있음
  • 0 <= k <= s.length

예제

Input: s = "ABAB", k = 2
Output: 4
Input: s = "AABABBA", k = 1
Output: 4

풀이 1

이 문제를 푸는 가장 단순 무식한 방법은 주어진 문자열에서 만들어낼 수 있는 모든 부분 문자열을 만든 후에 해당 문자열을 동일한 글자로 바꿀 수 있는지 따져보는 것입니다.

그럼 어떻게 하면 부분 문자열을 k번 바꿔서 모두 동일한 글자로 이뤄지게 만들 수 있을까요? 문자열에 가장 많이 들어있는 글자로 다른 글자들까지 모두 통일 시켜주면 될 것입니다.

예를 들어, A가 3개와 B가 2개로 이루어진 AABAB가 주어졌다고 가정해봅시다. 그 문자열은 AAAAA로 만들 수도 있고, BBBBB로 만들 수도 있을텐데요. B 글자 2개를 A로 바꿀 수도 있고, A 글자 3개를 B로 바꿀 수도 있을 것입니다. 만약에 k가 2라면 첫 번째 방법만 가능하고, k가 3이라면 이 두 가지 방법이 모두 가능할 것입니다. 다시 말해서 문자열의 길이에서 가장 많이 나온 글자의 수를 뺐을 때, k보다 크지 않다면 해당 문자열을 모두 동일한 글자로 바꿀 수 있습니다.

문자열 안에 각 글자가 몇 번씩 나왔는지는 해시 테이블(Hash Table)에 저장할 수 있을 것 같습니다.

그럼 이 알고리즘을 파이썬에 내장된 Counter 자료구조를 활용하여 구현해볼까요?

from collections import Counter

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        max_len = 0
        for start in range(len(s)):
            for end in range(start, len(s)):
                counter = Counter(s[start : end + 1])
                if end - start + 1 - counter.most_common(1)[0][1] <= k:
                    max_len = max(end - start + 1, max_len)
        return max_len

입력 문자열의 길이가 n이라고 했을 때 이 풀이는 시간 복잡도는 O(n^3)이 됩니다. 모든 부분 문자열을 구하는데 O(n^2)의 시간이 걸리고, 각 부분 문자열에 들어있는 각 글자의 개수를 알아내는데 또 O(n)의 시간이 걸리기 때문입니다. 성능이 너무 떨어져서 LeetCode에서 Time Limit Exceeded 오류가 나면서 통과가 되지 않을 것입니다.

공간 복잡도는 해시 테이블이 차지하는 메모리에 좌우가 될 텐데요. 문자열에 영어 대문자만 들어있기 때문에 해시 테이블에는 최대 26개의 글자가 저장될 수 있습니다. 따라서 공간 복잡도는 O(26) = O(1)이 됩니다.

풀이 2

횟수가 제한되어 있을 때 어떻게 하면 가장 효과적으로 글자를 바꿀 수 있을까요? 동일한 문자로 이루어진 가장 긴 부분 문자열을 만들 수 있는 지점에서 글자를 바꿔야 합니다.

이 문제처럼 부분 문자열을 찾을 때 매우 효율적인 풀이 기법이 있는데요. 바로 슬라이딩 윈도우(Sliding Window)입니다.

기본 아이디어는 두 개의 포인터를 사용하여 부분 문자열의 시작과 끝을 가리키게 하고, 윈도우의 길이를 유기적으로 늘렸다가 줄였다가 하면서 전체 문자열을 탐색해나가는 것입니다.

문제에서 주어진 두 번째 예제로 같이 차근차근 같이 생각을 해볼까요?

우선 두 개의 포인터를 모두 인덱스 0에 놓도록 하겠습니다. 두 개의 포인터가 가리키는 2개의 글자까지 부분 문자열에 포함시킵니다.

_
AABABBA => "A" => 길이 1 (시작 인덱스 0, 종료 인덱스 0)
카운터: {A: 1}

부분 문자열에 글자가 하나 밖에 없을 때 바꾸는 작업이 아무 의미가 없습니다. 아무리 글자를 바꾸어도 언제나 같은 글자로 이루어져 있기 때문입니다.

__
AABABBA => "AA" => 길이 2 (시작 인덱스 0, 종료 인덱스 1)
카운터: {A: 2}

종료 인덱스를 증가시키면, 부분 문자열은 A 글자 2개로 이루어집니다. 같은 글자로만 이루어져 있기 때문에 역시 어떤 글자로 바꿀 이유가 없습니다.

___
AABABBA => "AAB" => 길이 3 (시작 인덱스 0, 종료 인덱스 2)
카운터: {A: 2, B: 1}
부분 문자열의 길이 - 가장 많이 들어있는 글자의 수 = 3 - 2 = 1 == 1

종료 인덱스를 증가시키니, 부분 문자열에 처음으로 B 글자가 들어옵니다. 이 부분 문자열 안에 가장 많이 들어있는 문자는 A이므로, B를 A로 바꿔야 합니다.

그래서 이때, 부분 문자열의 길이에서 가장 많이 들어있는 글자의 수를 뺀 값이 k를 넘지 않는지 확인해야 합니다. 여기서는 부분 문자열의 길이가 3이고 가장 많이 들어있는 A의 개수가 2이므로, 이 둘을 빼면 1, 즉 k를 넘지 않습니다.

____
AABABBA => "AABA" => 길이 4 (시작 인덱스 0, 종료 인덱스 3)
카운터: {A: 3, B: 1}
부분 문자열의 길이 - 가장 많이 들어있는 글자의 수 = 4 - 3 = 1 == 1

종료 인덱스를 증가시키니, 부분 문자열에 A 글자가 들어옵니다. 이 부분 문자열 안에 가장 많이 들어있는 문자는 여전히 A이므로, B를 A로 바꿔야 합니다.

이전 단계와 동일한 방식으로 부분 문자열의 길이에서 가장 많이 들어있는 글자의 수를 빼면 아직, k를 넘지는 않습니다.

_____
AABABBA => "AABAB" => 길이 5 (시작 인덱스 0, 종료 인덱스 4)
카운터: {A: 3, B: 2}
부분 문자열의 길이 - 가장 많이 들어있는 글자의 수 = 5 - 3 = 2 > 1

종료 인덱스를 증가시키니, 부분 문자열에 다시 B 글자가 들어옵니다. 이 부분 문자열 안에 가장 많이 들어있는 문자는 여전히 A이므로, B를 A로 바꿔야 하는데요.

이번에는 이전 단계와 다르게 부분 문자열의 길이에서 가장 많이 들어있는 글자의 수를 뺀 값이 k보다 커집니다. 따라서 우리는 시작 인덱스를 증가시켜서 문자열의 길이를 줄여줘야 합니다.

 ____
AABABBA => "AABAB" => 길이 4 (시작 인덱스 1, 종료 인덱스 4)
카운터: {A: 2, B: 2}
부분 문자열의 길이 - 가장 많이 들어있는 글자의 수 = 4 - 2 = 2 > 1

시작 인덱스를 증가시키니, 부분 문자열에 A 글자가 빠집니다. 이 부분 문자열 안에는 A와 B가 동일하게 2개씩 들어 있습니다.

여전히 부분 문자열의 길이에서 가장 많이 들어있는 글자의 수를 뺀 값이 k보다 큽니다. 따라서 우리는 시작 인덱스를 증가시켜서 문자열의 길이를 줄여줘야 합니다.

  ___
AABABBA => "AABAB" => 길이 3 (시작 인덱스 2, 종료 인덱스 4)
카운터: {A: 1, B: 2}
부분 문자열의 길이 - 가장 많이 들어있는 글자의 수 = 3 - 2 = 1 == 1

시작 인덱스를 증가시키니, 부분 문자열에 A 글자가 빠집니다. 이제 부분 문자열 안에는 B가 2개로 가장 많이 들어 있습니다.

부분 문자열의 길이에서 가장 많이 들어있는 글자의 수를 빼면 k와 같아 집니다. 따라서 우리는 종료 인덱스를 증가시켜서 문자열의 길이를 늘려줘야 합니다.

  ____
AABABBA => "AABAB" => 길이 4 (시작 인덱스 2, 종료 인덱스 5)
카운터: {A: 1, B: 3}
부분 문자열의 길이 - 가장 많이 들어있는 글자의 수 = 4 - 3 = 1 == 1

종료 인덱스를 증가시키니, 부분 문자열에 B 글자가 들어옵니다. 이 부분 문자열 안에 가장 많이 들어있는 문자는 여전히 B이므로, A를 B로 바꿔야 합니다.

여기서는 부분 문자열의 길이가 4이고 가장 많이 들어있는 B의 개수가 3이므로, 이 둘을 빼면 1, 즉 k를 넘지 않습니다. 또 종료 인덱스를 증가시킬 수 있습니다.

위와 같은 과정을 반복하면서 슬라이딩 윈도우를 왼쪽에서 오른쪽 끝까지 움직이면서 k번 글자를 바꿔서 만들 수 있는 같은 문자로 이루어진 가장 긴 문자열을 찾을 수 있을 것입니다. 이 알고리즘을 파이썬으로 구현해보겠습니다.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        max_len = 0
        counter = {}
        start, end = 0, 0
        while end < len(s):
            counter[s[end]] = counter.get(s[end], 0) + 1
            while end - start + 1 - max(counter.values()) > k:
                counter[s[start]] -= 1
                start += 1
            max_len = max(end - start + 1, max_len)
            end += 1
        return max_len

종료 인덱스는 항상 1씩 증가하니, while 문 대신에 for 문을 써도 되겠네요.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        max_len = 0
        counter = {}
        start = 0
        for end in range(len(s)):
            counter[s[end]] = counter.get(s[end], 0) + 1
            while end - start + 1 - max(counter.values()) > k:
                counter[s[start]] -= 1
                start += 1
            max_len = max(end - start + 1, max_len)
        return max_len

이 풀이의 시간 복잡도는 두 개의 포인터를 사용하여 루프를 도는 O(n)의 시간이 걸리고, 가장 많이 들어있는 글자의 수를 찾는데는 O(26)의 시간이 걸려서, O(26n) = O(n)이 되겠습니다.

최적화

가장 많이 들어있는 글자의 수를 변수에 저장하면 매번 해시 테이블에 가장 많은 들어있는 글자의 수를 찾아낼 필요가 없습니다.

아래와 같이 코드를 살짝 수정해주면 우리는 윈도우(window)에 새롭게 추가된 종료 포인터가 가리키는 글자의 수가 여태까지 가장 많이 들어있었던 글자의 수보다 클 때만, 시작 포인터를 가리는 글자를 윈도우에서 제거하기 시작합니다. 이를 통해서 반복되는 글자를 포함하지 않는 가장 긴 부분 문자열이 앞에서 발견되었을 경우, 그 뒤에 나오는 반복되는 글자를 포함하지만 더 짧은 문자열을 모두 건너뛸 수가 있기 때문에 더 효율적입니다.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        max_len, max_cnt = 0, 0
        counter = {}
        start = 0
        for end in range(len(s)):
            counter[s[end]] = counter.get(s[end], 0) + 1
            max_cnt = max(counter[s[end]], max_cnt)
            while end - start + 1 - max_cnt > k:
                counter[s[start]] -= 1
                start += 1
            max_len = max(end - start + 1, max_len)
        return max_len

그런데 이렇게 최적화를 해주더라도 빅오 계산법 기준으로는 이전 풀이와 의미있는 복잡도 차이가 나지는 않습니다. 어차피 해시 테이블에는 최대 26개의 영어 대문자에 대한 개수만 저장이 되어 있기 때문입니다.

마치면서

이 문제가 너무 어려우셨다면 비슷하지만 좀 더 쉬운 문제인 Longest Substring Without Repeating Characters도 풀어보시라고 추천드립니다.