[Leetcode] 424. Longest Repeating Character Replacement

문제

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.
Return the length of the longest substring containing the same letter you can get after performing the above operations.
 
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. There may exists other ways to achieve this answer too.
 
Constraints:
1 <= s.length <= 105s consists of only uppercase English letters.0 <= k <= s.length

 

풀이 

이 문제는 다른 sliding window랑 비슷하지만 모든 알파벳의 변화를 고려해야한다.

여기서 중요한 점은 #changes 를 일일이 카운트하는게 아니라 current window size - maxfreq 로 찾는 점이다.

current window size - maxfreq 는 한 알파벳을 제외한 알파벳들을 의미하고 그 한 알파벳을 제외한 변화의 수를 구한다.

right = 0 -> freq[A] = 1 -> maxFreq = 1 -> valid -> maxLength = 1
right = 1 -> freq[A] = 2 -> maxFreq = 2 -> valid -> maxLength = 2
right = 2 -> freq[B] = 1 -> maxFreq = 2 -> valid -> maxLength = 3
right = 3 -> freq[A] = 3 -> maxFreq = 3 -> valid -> maxLength = 4
right = 4 -> freq[B] = 2 -> Changes needed=(5-3)=2 > k -> shrink left
          left=1 -> freq[A]=2 -> valid -> maxLength remains unchanged

퍼플렉시티가 위의 표로 잘 설명해주었다. 

 

 

코드

int characterReplacement(char* s, int k) {
    int n = strlen(s);
    int freq[26] = {0};
    int maxfreq = 0;
    int left = 0, maxLength = 0;

    for(int right = 0; s[right]; right++) {
        freq[s[right]-'A']++;

        if(freq[s[right]-'A'] > maxfreq) maxfreq = freq[s[right]-'A'];

        // (current window size - maxFreq) = Changes made
        if((right-left+1) - maxfreq > k) {
            freq[s[left]-'A']--;
            left++;
        }
        if((right-left+1) > maxLength) maxLength = (right-left+1);
    }
    return maxLength;
}