[LeetCode#424] Longest Repeating Character Replacement

 

❒ Description

---

날짜	2024.11.15 (금)
레벨	Medium
링크	https://leetcode.com/problems/longest-repeating-character-replacement/description/
알고리즘	슬라이딩 윈도우, 투 포인터
시간 복잡도	O(n²)
소요시간	2hour
풀이 확인 여부	Y

 

 

 

 

 

❒ 문제 분석

---

[🔥핵심 아이디어] 윈도우 내에 있는 문제 중, 교체할 수 있는 문자의 갯수를 고려해야 한다.

 

현재 윈도우 내에서 교체할 수 있는 문자의 수를 구할 수 있어야 한다.

현재 교체할 수 있는 문자의 수 = (right - left + 1) - maxCharCount

 

1. 최대 길이를 구해야 하기 때문에 최초에는 right 커서만 한 칸 씩 움직인다.

2. right 커서를 움직이면서 현재 right 커서가 가리키는 문자를 counting 해준다.

3. 만약 현재 교체할 수 있는 문자의 수가 k(교체 횟수) 보다 많다면, left 커서를 한 칸 이동해준다.

 

 

 

 

 

❒ 문제 풀이

---

public class Quiz424 {

    private int maxCount = 0;
    private int longest = 0;
    private int maxReplaceCount = 0;

    public int characterReplacement(String s, int k) {
        int left = 0;
        maxReplaceCount = k;

        int[] countMap = new int[26];
        for (int right = 0; right < s.length(); right++) {
            int charAtRightCursor = s.charAt(right) - 'A';
            countMap[charAtRightCursor]++;
            maxCount = Math.max(maxCount, countMap[charAtRightCursor]);

            while (needToResizeWindow(left, right)) {
                int charAtLeftCursor = s.charAt(left) - 'A';
                countMap[charAtLeftCursor]--;
                left++;
            }
            longest = Math.max(longest, right - left + 1);
        }
        return longest;
    }

    private boolean needToResizeWindow(int left, int right) {
        return right - left + 1 - maxCount > maxReplaceCount;
    }
}

 

 

 

 

 

---