424. Longest Repeating Character Replacement

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

Longest Repeating Character Replacement - LeetCode

 

Given a string s that consists of only uppercase English letters, you can perform at most k operations on that string.

In one operation, you can choose any character of the string and change it to any other uppercase English character.

Find the length of the longest sub-string containing all repeating letters you can get after performing the above operations.

Note:
Both the string's length and k will not exceed 104.

Example 1:

Input: s = "ABAB", k = 2 Output: 4 Explanation: Replace the two 'A's with two 'B's or vice versa.

 

Example 2:

Input: s = "AABABBA", k = 1 Output: 4 Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4.

 

 

---

길이가 N인 문자열이 주어질때 임의의 문자 K개를 우리가 원하는 문자로 바꿀 수 있으며

 

이때 동일한 문자들이 연달아 이루어진 부분문자열의 최대 갯수가 몇개인지 알아내는 문제이다.

 

AABBBCBBCDEAABB

K = 1

 

위와같은 문자열에선 제일 왼쪽의 C를 B로 바꾸면 최대 길이가 6이된다.

 

문자를 우리가 원하는대로 바꿀수가 있기 때문에 선형 탐색을 해 나가면서 특정 문자를 기준으로 해당 문자와 다른 문자가 몇개 나오는지를 세는 방식으로 탐색하면 O{N^2} 만큼의 시간이 걸리게 된다.

 

하지만 two pointers 알고리즘을 통해 2*N 만큼의 연산 속도가 이루어지게 할 수 있다.

 

부분 문자열의 시작을 가리키는 index start와 끝을 가리키는 index i 그리고 부분 문자열내의 각 문자가 몇개 존재하는지 알기위한 배열 int cnts[26] 를 통해 "부분 문자열의 길이 - 부분 문자열 내에 제일 많이 나온 문자의 갯수" 를 해주면 해당 부분 문자열에서 총 몇개의 문자를 바꿔야 하는지를 알 수 있다. 이 값이 K를 넘으면 안된다.

 

즉 핵심은

 

• 부분 배열 내에서 제일 많이 나온 문자를 기준으로 이외의 문자를 K치환 가능해야 한다. 이조건이 충족되지 못하면 충족될때까지 start를 옮겨야 한다.
• '최대 길이'를 구하는 것이므로 부분 배열의 길이가 다시 작아질 필요는 없다. 중요한건 "부분 배열이 더 길어질수 있냐"는 것이다.

그럼 제일 많이 나온 문자를 어떻게 찾아야 할까? cnts 배열을 선형 탐색해도 되겠지만 시간을 더 줄이고싶다. 중요한건 index i는 한칸씩 늘어난다는것이다. 즉, 부분문자열의 길이는 한칸씩 늘거나 변하지 않는다는 것이다.  즉, 부분 문자열 내의 각 문자의 갯수들도 한칸씩 늘거나 줄거나 변함 없다는것이다. 그렇기에 항상 이번에 늘어난 문자의 갯수와 기존에 최대 길이였던 문자의 갯수를 비교하기만 하면 max(cnts) 를 얻을 수 있다.

 

class Solution {
public:
    int characterReplacement(string s, int k) {
        
        int N = s.size();
        int ret = 0, maxCnt = 0, start = 0;
        int cnts[26] = {0,};
        
        for (int i = 0; i < N; ++i) {
            cnts[s[i] - 'A']++;
            maxCnt = max(cnts[s[i] - 'A'], maxCnt);
            
            if ((i - start + 1) - (maxCnt) > k) {
                cnts[s[start] - 'A']--;
                start++;
            }
            
            ret = max(ret, i - start + 1);
        }
        
        return ret;
    }
};

 

 

나름대로 정리했지만 지금도 직관적으로 이해하기가 쉽지 않다.

그래도 잘 익혀놓으면 유용해 보이는 개념이다.