[LeetCode] Longest Repeating Character Replacement (Java)

✉️문제

https://leetcode.com/problems/longest-repeating-character-replacement/description/

 

📝 접근

1. 투 포인터 알고리즘을 기본적으로 이용한다. (left, right 포인터)
2. right포인터를 오른쪽으로 이동시키면서 가장 빈번하게 나타난 알파벳의 개수를 기억한다. 
   • (right - left + 1 - maxFrequency)는 uppercase로 바꾼 횟수를 의미한다.
3. 만약 right - left + 1 - maxFrequency > k 이면 left를 증가시킨다. 
   
   • left를 증가시킬 때 마다 maxFrequecy를 감소시킬 필요는 없다.
   • 답은 가장 긴 길이를 구하는 것이며 maxF가 감소될 때 정답이 갱신될 수 없다.

 

🗝 문제풀이

class Solution {
    public int characterReplacement(String s, int k) {
        int[] ch = new int['Z' - 'A' + 1];

        int max = Integer.MIN_VALUE;
        int maxLen = 0;
        for(int left = 0, right = 0; right < s.length(); right++) {
            int index = s.charAt(right) - 'A';
            ch[index]++;
            max = Math.max(max, ch[index]);
            while(right - left + 1 - max > k) {
                ch[s.charAt(left) - 'A']--;
                left++;
            }

            maxLen = Math.max(maxLen, right - left + 1);
            // System.out.println(max);
        }

        return maxLen;
    }
}