[Leetcode] 424. Longest Repeating Character Replacement

Identifying the Problem

주어진 문자열 s에서 최대 k번 문자열을 교체하여 가능한 가장 긴 중복 문자열의 길이를 리턴한다.

 

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

Explanation: 4번째 A를 B로 1번 교체하므로 길이가 4인 BBBB 가장 긴 중복 수열을 만들었다.

Organizing thoughts

핵심 아이디어는 아래 유튜브를 참고했다.

 

Sourcecode

소스코드 출처

 

C++ Sliding Window Solution O(N) - LeetCode Discuss

class Solution {
public:
    int characterReplacement(string s, int k) {
        
        int sl = s.length(); // 문자열의 길이
        
        vector<int>char_freq(26,0); //A~Z의 빈도를 저장할 LetterMap
        
        int result = INT_MIN; //결과 값
        
        //투 포인터
        int first = 0;
        int last =  0;
        
        // 저장한 빈도 중 가장 큰 빈도를 저장할 변수
        int max_freq = 0;
        
       // last 포인터가 끝까지 갈 때까지 반복
        while(last < sl)
        {
            char_freq[s[last]-'A']++; // 탐색 글자의 빈도 증가
            max_freq = max(max_freq,char_freq[s[last]-'A']); 
            //문자열 중 가장 큰 빈도를 가진 문자의 개수

            // window 크기 - max_freq 가 k 보다 작으면 window의 크기를 넓히면 되지만
            // k보다 클 경우 window의 크기를 줄여야한다.
            if((last-first+1 - max_freq)> k)
            {
                char_freq[s[first]-'A']--; //windown를 오른쪽으로 옮기면서                 
                first++;	//왼쪽 빈도 줄이기
            }

            result = max(result,last-first+1); //window길이와 이전 max의 값을 비교
            last++; //window 크기 증가
        }
        
        return result;
    }
};

 

New things learned

 

 

[Algorithm] 슬라이딩 윈도우(Sliding Window) 알고리즘