Longest Repeating Character Replacement

Q: Longest Repeating Character Replacement의 시간 복잡도는 얼마인가요?

하나의 윈도우를 사용하는 해결 방법은 s 의 길이인 n에 대해 O(n) 시간에 실행됩니다. right 는 각 문자를 한 번씩 방문하고 left 는 단계마다 최대 한 번 이동합니다. 추가 공간은 O(1)을 사용하며, 26개의 개수와 몇 개의 정수만 필요합니다.

보통슬라이딩 윈도우

+10

대문자 영문자로 이루어진 문자열 s와 정수 k가 주어집니다. s에서 최대 k개의 위치를 선택하고, 각 위치의 문자를 다른 대문자로 바꿀 수 있습니다.

변경을 완료한 후 동일한 문자가 반복되는 가장 긴 부분 문자열, 즉 서로 인접한 문자들의 연속 구간의 길이를 반환하세요.

함수

characterReplacement(s: string, k: integer) → integer

sstring: 대문자 문자열
kinteger: 변경할 수 있는 최대 글자 수
반환값integer: 만들 수 있는, 같은 문자가 반복되는 가장 긴 부분 문자열의 길이

제약 조건

1 ≤ s.length ≤ 5 × 10⁴
s에는 영어 대문자만 들어 있습니다.
0 ≤ k ≤ s.length

예제

입력: s = "BAAACAB"k = 1
출력: 5
설명: C를 A로 바꾸면 인덱스 1부터 5까지가 AAAAA가 됩니다. 6글자로 이루어진 두 구간 모두 B와 C를 포함하므로 두 번 바꿔야 합니다.

입력: s = "AABBBAB"k = 2
출력: 6
설명: 인덱스 1부터 6까지는 ABBBAB이고, 두 A 문자를 모두 바꾸면 BBBBBB가 됩니다. 전체 문자열에는 7개 중 B 문자가 4개뿐이므로 3번 바꿔야 합니다.

후속 질문

26개의 대문자 대신 s에 어떤 문자든 저장할 수 있다면 무엇이 달라질까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

부분 문자열에서 가장 많이 나타나는 문자는 유지하고 나머지는 바꾸세요. 가장 많이 나타나는 문자가 top번 등장하는 길이 len의 부분 문자열을 바꾸려면 len - top번 변경해야 합니다. 슬라이딩 윈도우를 사용하면 한 번의 순회로 len - top ≤ k를 만족하는 가장 긴 부분 문자열을 찾을 수 있습니다. 윈도우를 줄일 필요가 없고 top도 감소하지 않기 때문입니다.

모든 부분 문자열을 확인하세요

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

각 시작 위치마다 끝을 한 글자씩 늘리고, 글자별 개수와 top을 갱신한 다음 len - top ≤ k를 검사합니다. 새로운 부분 문자열마다 개수를 처음부터 세는 대신 한 번만 갱신하고, 모든 부분 문자열을 검사하므로 도달할 수 있는 가장 긴 부분 문자열을 놓치지 않습니다.

길이가 n인 문자열에는 약 n²/2개의 부분 문자열이 있습니다. n = 5 × 10^4일 때 검사 횟수는 1.25 × 10^9회입니다.

알고리즘

best를 0으로 설정합니다.
각 시작 인덱스마다 26개의 카운트와 top을 0으로 초기화합니다.
end를 시작 위치부터 마지막 인덱스까지 이동합니다. s[end]의 카운트를 증가시키고, 해당 카운트가 가장 높은 값이 되면 top을 올립니다.
end - start + 1 - top ≤ k이면, 길이가 best보다 클 경우 저장합니다.
best를 반환합니다.

def characterReplacement(s, k):
    n = len(s)
    best = 0
    for start in range(n):
        count = [0] * 26  # letters in s[start..end]
        top = 0           # count of the most common letter there
        for end in range(start, n):
            c = ord(s[end]) - ord('A')
            count[c] += 1
            top = max(top, count[c])
            # Every letter that is not the most common one must change.
            if end - start + 1 - top <= k:
                best = max(best, end - start + 1)
    return best

대상 문자마다 슬라이딩 윈도우 하나

핵심 아이디어

먼저 마지막 문자를 선택하세요. 구간이 모두 A로 끝나게 하려면 k개 이하의 A가 아닌 문자를 포함하는 가장 긴 부분 문자열을 찾으면 됩니다.

문자열을 따라 right를 이동하면서 윈도우 안의 목표 문자가 아닌 문자의 개수를 셉니다. 개수가 k를 초과하면 다시 k개가 될 때까지 left를 앞으로 이동합니다. 너무 많은 비용이 드는 윈도우는 늘어나도 계속 비용이 너무 많이 들기 때문에 left는 뒤로 움직이지 않으며, 각 right에서 해당 위치에서 끝나는 가장 긴 유효한 윈도우를 얻습니다.

26개 문자 모두에 대해 실행하고 최댓값을 유지하세요. 최대 5 × 10^4개의 문자에 대해 선형으로 26번 순회합니다. 알파벳의 크기가 작기 때문에 O(n)을 유지할 수 있습니다.

알고리즘

각 대상 문자 A부터 Z까지, left = 0 및 others = 0으로 윈도우를 시작합니다.
문자열을 따라 right를 이동합니다. s[right]가 대상 문자가 아니면 others를 1 증가시킵니다.
others > k인 동안 left를 앞으로 이동하고, 윈도우에서 빠져나가는 문자가 대상 문자가 아니면 1을 뺍니다.
right - left + 1이 best보다 크면 저장합니다.
26개 문자를 모두 확인한 후 best를 반환합니다.

def characterReplacement(s, k):
    best = 0
    for target in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
        left = 0
        others = 0  # letters in s[left..right] that are not target
        for right in range(len(s)):
            if s[right] != target:
                others += 1
            # Too many letters to change: drop letters from the left.
            while others > k:
                if s[left] != target:
                    others -= 1
                left += 1
            best = max(best, right - left + 1)
    return best

절대 줄어들지 않는 창 하나

핵심 아이디어

윈도우의 26개 문자 빈도와 가장 높은 빈도인 top을 유지하세요. s[right]를 추가했을 때 윈도우를 만들기 위해 바꿔야 하는 문자의 수가 너무 많아지면 왼쪽에서 문자 하나를 제거하세요. 윈도우가 이동하면서 길이는 그대로 유지됩니다. 더 긴 윈도우만 기록을 깰 수 있기 때문입니다. 그렇지 않으면 길이가 1 늘어납니다. 윈도우의 길이는 항상 지금까지의 최댓값이므로 답은 n - left입니다.

문자가 빠져나가도 실제 빈도보다 높아졌더라도 top은 그대로 두세요. 윈도우가 이동한 뒤 길이는 정확히 top + k이므로, 윈도우를 늘리려면 어떤 문자가 top + 1번 나타나야 하고, 그 순간 top도 함께 올라갑니다. 오래된 top 값은 윈도우가 이동하게 만들 수 있을 뿐이며, 이동한다고 해서 기록을 잃을 수는 없습니다.

k = 1일 때 BAAACAB에서 BAAAC는 문자 2개를 바꿔야 하므로 AAAC로 이동합니다. 다음 A가 들어오면 top이 4로 올라가고 윈도우는 길이 5인 AAACA로 늘어납니다.

알고리즘

26개의 개수를 유지하고, left = 0과 top = 0으로 설정합니다.
문자열을 따라 right를 이동합니다. s[right]를 해당 개수에 더하고, 그 개수가 이제 더 높다면 top을 올립니다.
right - left + 1 - top > k이면 개수에서 s[left]를 빼고 left를 한 칸 이동합니다. top은 절대 낮추지 않습니다.
최종 윈도우 길이인 n - left를 반환합니다.

def characterReplacement(s, k):
    count = [0] * 26  # letters inside the window s[left..right]
    left = 0
    top = 0  # the highest count any letter has reached in a window
    for right in range(len(s)):
        c = ord(s[right]) - ord('A')
        count[c] += 1
        top = max(top, count[c])
        # Needs more than k changes: slide the window instead of growing it.
        if right - left + 1 - top > k:
            count[ord(s[left]) - ord('A')] -= 1
            left += 1
    # The window only grew when a longer valid substring was found.
    return len(s) - left

함정과 경계 사례

가장 긴 연속 구간에 k를 더하는 것. AAAB에서 k = 3이면 6이 되어 문자열보다 길어집니다. BAAACAB에서 k = 1이면 4가 되지만, C를 바꾸면 두 구간이 합쳐져 5가 됩니다.
윈도우에서 가장 많이 나온 문자가 아니라 첫 번째 문자를 기준으로 변경 횟수를 세는 것. BAAA는 세 번이 아니라 한 번 바꾸면 됩니다.
윈도우를 while로 줄이고 실제 최댓값을 다시 계산하는 루프에서 n - left를 반환하는 것. 이 경우 윈도우는 짧아지므로 별도의 best를 유지하세요.
윈도우의 길이를 right - left로 계산하는 것. 양 끝이 모두 윈도우에 포함되므로 1을 더하세요.

자주 묻는 질문3

Longest Repeating Character Replacement의 시간 복잡도는 얼마인가요?

하나의 윈도우를 사용하는 해결 방법은 s의 길이인 n에 대해 O(n) 시간에 실행됩니다. right는 각 문자를 한 번씩 방문하고 left는 단계마다 최대 한 번 이동합니다. 추가 공간은 O(1)을 사용하며, 26개의 개수와 몇 개의 정수만 필요합니다.

이것은 중복 문자가 없는 가장 긴 부분 문자열과 어떻게 다른가요?

둘 다 문자열에서 두 개의 경계를 이동하지만, 유효한 윈도우의 규칙은 다릅니다. 그 문제에서는 문자가 반복되면 안 되므로, 반복이 사라질 때까지 윈도우를 줄입니다. 여기서는 길이에서 최빈 문자 개수를 뺀 값이 최대 k여야 하므로, 윈도우가 고정된 길이로 이동할 수 있습니다.

이 문제는 이진 탐색으로 해결할 수 있나요?

네. 길이가 L인 부분 문자열에 도달할 수 있다면 그 안에 있는 더 짧은 모든 부분 문자열에도 도달할 수 있으므로, L에 대해 이분 탐색을 할 수 있습니다. 각 L에 대해 해당 길이의 고정된 윈도우를 이동하면서 변경이 k번 이하로 필요한 위치가 있는지 확인합니다. 이는 O(n log n)으로, 윈도우 하나만 사용하는 해결 방법보다 느립니다.

def characterReplacement(s, k):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

s = "BAAACAB"
k = 1

예상 출력

Longest Repeating Character Replacement

함수

제약 조건

예제

힌트

풀이

모든 부분 문자열을 확인하세요

대상 문자마다 슬라이딩 윈도우 하나

절대 줄어들지 않는 창 하나

함정과 경계 사례

자주 묻는 질문3

비슷한 문제