Leetcode - 424. Longest Repeating Character Replacement

문제

대문자로 구성된 문자열이 주어지고, 아무 문자로 바꿀수 있는 횟수 k가 주어질때, 동일한 문자로 구성된 substring의 최대 갯수는?

Input: s = "ABAB", k = 2
Output: 4

Input: s = "AABABBA", k = 1
Output: 4

해결 O(n)

생각하기 어려웠던 문제였다. discussion을 좀 참고했음. right와 left를 O(n)동안 하나씩만 이동해도 결과를 얻을수 있는게 직관적으로 와닿지 않음. right를 for문에서 하나씩 증가. 각 루프에서 해당 right까지 내에서 최대 길이 보장됨을 의미. 문자열길이에서 해당 문자열중에 가장 freq가 많은 문자 갯수 를 뺀갯수가 k개를 초과하면 left를 증가시킨다.

속도는 100% 나옴.

#define max(a,b) (((a) > (b)) ? (a) : (b))
int characterReplacement(char * s, int k){
    int freq[26] = {0};
    int maxfreq = 0;
    int ssize = strlen(s);
    int left = 0, right = 0;
    int maxlen = 0;
    
    for (; right < ssize; right++) {
        /* update s[right] freq */
        freq[s[right] - 'A']++;
        maxfreq = max(maxfreq, freq[s[right] - 'A']);
        
        /* if target charactors to change is larger than k */ 
        /* len = right - left + 1 */
        if (right - left + 1 - maxfreq > k) {
            freq[s[left] - 'A']--;
            left++;
        } else {
            maxlen = max(right - left + 1, maxlen);
        }
    }
    return maxlen;
}