[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.

Returnthe length of the longest substring containing the same letter you can get after performing the above operations.

문자열 s와 정수가 주어지면 문자열의 문자를 선택하여 다른 대문자 영어 문자로 변경할 수 있습니다. 이 연산은 최대 k번까지 수행할 수 있습니다.
위의 연산을 수행한 후 얻을 수 있는 동일한 문자를 포함하는 가장 긴 부분 문자열의 길이를 반환합니다.

 

 

 

내 생각

 

그러니까 다른 문자열로 바꿨을 때, 가장 긴 부분 문자열을 찾는 문제이다. 문자열을 한번씩 돌면서 가장 긴 부분 문자열을 가지는 것을 찾고, 그 길이를 반환하면 된다. 슬라이딩 윈도우를 이용해서 left와 right로 현재 윈도우를 만들어가면서 현재 윈도우에서 가장 빈도가 높은 문자의 빈도를 찾고, 유지한다. 그리고 그 빈도를 카운터 계산하면서 현재 윈도우에서 가장 높은 문자의 빈도를 찾으면 된다.

 

중요한건 예외인 부분인데, 윈도우의 길이(right - left + 1)에서 가장 빈도가 높은 문자의 수(maxCount)를 뺀 값이 k보다 크면 교체할 문자가 많다는 뜻이므로 윈도우를 왼쪽으로 한칸 줄여야 한다. 

 

* 대문자char - 'A' = 배열의 인덱스 화

ex) 'A' - 'A' = 65 - 65 = 0 → 인덱스 0

 

 

내 코드

class Solution {
    public int characterReplacement(String s, int k) {
        //현재 윈도우 내의 문자 빈도
        int[] cnt = new int[26];
        int left = 0, right = 0;
        int maxCnt = 0;
        int maxLength = 0;

        //윈도우 확장
        while (right < s.length()){
            //현재 문자빈도수 ++
            char current = s.charAt(right);
            cnt[current - 'A']++;
            //현재 윈도우에서 빈도가 가장 높은 문자의 빈도 업데이트
            maxCnt = Math.max(maxCnt, cnt[current - 'A']);

            //현재 윈도우가 유효하지 않다면?
            if (right - left + 1 - maxCnt > k){
                char leftChar = s.charAt(left);
                cnt[leftChar - 'A']--;
                //왼쪽으로 윈도우 줄이기
                left++;
            }
        //윈도우 최대 길이 업데이트
        maxLength = Math.max(maxLength, right - left + 1);
        //오른쪽으로 윈도우 확장
        right++;
        }
        return maxLength;
    }
}