[leetcode 424] Longest Repeating Character Replacement

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.

 

 

풀이

- 슬라이딩 윈도우 + map 사용

 

기존 슬라이딩 윈도우와 동일하게 start, end를 설정한다.

int cnt[26]은 범위 안에(start, end 사이) 등장하는 문자수를 체크한다. 

end는 매번 +1, start가 움직이는 조건은 범위 안에 다른 문자가 k개 이상일때 이다. 

- 범위 안에 다른 문자가 k개 이상인지 세는 방법: 문자가 등장할 때마다 해당 문자의 개수를 +1 한다. 동시에 문자의 최대 등장 횟수(maxCnt)를 저장한다. 

- end-start + 1은 문자열 길이를 의미한다.

- 만약 end-start+1 - maxCnt ==0이라면 문자열의 모든 문자가 동일한 문자인 것을 의미한다. end-start +1 -maxCnt >0 이라는 것은 다른 문자가 하나라도 존재한다는 의미

- 따라서 end-start+1-maxCnt > k이면 범위 안에 다른 문자가 k개 이상 존재한다는 것을 의미한다. 이 때 start를 1 증가시키고 cnt[26]배열을 업뎃한다.

 

코드

class Solution {
public:
    int characterReplacement(string s, int k) {
        
        int start=0, maxCnt=0, result=0;
        
        int cnt[26] = {0,};
        
        for(int end = 0; end<s.length(); end++){
            char cur = s[end];
            cnt[cur - 'A']++;
            maxCnt = max(maxCnt, cnt[cur-'A']);
            
            if(end-start+1 - maxCnt > k){
                cnt[s[start] - 'A']--;
                start++;
            }
            
            result = max(result, end-start+1);
        }
        
        return result;
        
    }
};