Longest Repeating Character Replacement

부분 문자열 하나를 수정합니다. 어떤 문자로 바꿔야 할까요? 이미 가장 많이 나타나는 문자로 바꾸면 됩니다. 다른 모든 문자를 바꿔야 하기 때문입니다. 따라서 가장 많이 나타나는 문자가 top번 등장하는 길이 len의 부분 문자열은 len - top번 수정해야 하며, 그 횟수가 k 이하라면 만들 수 있습니다.

모든 부분 문자열을 시도해 봅니다. 시작 위치마다 끝 위치를 한 글자씩 늘리면서 각 문자의 개수를 세고, 진행하면서 top을 갱신합니다. 그러면 새 부분 문자열마다 개수를 처음부터 다시 세는 대신 한 번만 갱신하면 됩니다. 모든 부분 문자열을 확인하므로 만들 수 있는 가장 긴 부분 문자열을 놓칠 수 없습니다.

문자열의 길이가 n일 때 부분 문자열은 약 n²/2개이므로 느립니다. n = 5 × 10^4이면 확인 횟수가 1.25 × 10^9회에 달해 제한 시간 안에 처리하기에는 훨씬 많습니다.

질문을 반대로 생각하고 먼저 문자를 선택하세요. 마지막 문자열이 모두 A라면, 질문은 다음과 같이 바뀝니다. A가 아닌 문자가 최대 k개 포함된 가장 긴 부분 문자열은 무엇일까요? 이는 전형적인 슬라이딩 윈도우 문제입니다.

문자열에서 right를 이동하며 윈도우 안에 있는 목표 문자가 아닌 문자의 개수를 셉니다. 그 개수가 k를 초과하면 다시 k가 될 때까지 left를 앞으로 이동합니다. 윈도우를 키우면 바꿔야 하는 문자만 추가될 수 있으므로, 비용이 너무 큰 윈도우는 커져도 계속 비용이 너무 크며 left를 뒤로 이동할 필요는 없습니다. 각 right에 대해 유지하는 윈도우는 해당 위치에서 끝나는 조건을 만족하는 가장 긴 윈도우입니다.

26개 문자 모두에 대해 이 과정을 실행하고 가장 긴 길이를 유지합니다. 각 실행은 O(n)이므로 총 26회 반복하며, n = 5 × 10^4일 때 약 1.3 × 10^6단계입니다. 이는 선형 시간 알고리즘이지만 문자열을 26번 읽으며, 알파벳이 작기 때문에 가능한 방법입니다.

하나의 윈도우에서 모든 문자를 처리합니다. 윈도우 안에서 26개 문자 각각의 개수와 가장 높은 개수인 top을 유지합니다. 윈도우에는 length - top번의 변경이 필요하므로, 그 값이 k 이하이면 유효합니다.

첫 번째 사실: 윈도우는 줄어들 필요가 없습니다. 지금까지 찾은 최장 길이보다 더 길어지는 경우에만 관심이 있으므로, s[right]를 추가했을 때 윈도우를 유효하게 만들기 위한 변경 횟수가 너무 많아지면 왼쪽에서 문자 하나를 제거합니다. 윈도우는 한 칸 이동하고 길이는 그대로 유지됩니다. 윈도우가 유효하면 길이가 1 증가합니다. 따라서 윈도우의 길이는 항상 지금까지 찾은 최장 길이이며, 마지막에 답은 n - left입니다.

두 번째 사실: top은 줄어들 필요가 없습니다. 왼쪽에서 문자가 빠져나갈 때 top은 그대로 두므로, 윈도우 안의 실제 개수보다 클 수도 있습니다. 그래도 괜찮습니다. 한 칸 이동한 후 윈도우 길이는 정확히 top + k이므로, 윈도우를 늘리려면 윈도우 안에 top + 1번 나타나는 문자가 필요하고, 그 순간 top도 함께 증가합니다. 오래된 top 값 때문에 윈도우가 이동할 수는 있지만, 잘못해서 길어지지는 않습니다. 이동해도 손해가 없는 이유는 기록을 깨려면 더 긴 윈도우가 필요하기 때문입니다.

BAAACAB에서 k = 1일 때, 윈도우는 BAAA까지 늘어난 다음 BAAAC는 변경 2번이 필요하므로 AAAC까지 이동합니다. 다음 A를 추가하면 top이 4로 증가하고, 윈도우는 길이가 5인 AAACA까지 늘어납니다. 마지막 B가 윈도우를 한 번 더 이동하게 하므로 답은 5입니다.