LeetCode 424. 가장 긴 반복 문자 대체

LeetCode 424. 가장 긴 반복 문자 대체

문제

대문자로 구성된 문자열 s가 주어졌을 때 k번만큼의 변경으로 만들 수 있는 연속으로 반복된 문자열의 가장 긴 길이를 출력하라.

입력

ex 1 ) s = "AAABBCD", k = 2
ex 2 ) s = "AABABBA", k = 1

출력

1. 5
2. 4

풀이

접근 방법

ABABACD

ABBAACD

투 포인터와 슬라이딩 윈도우를 이용하여 해결하여야 한다.

예시 2 를 이용한 풀이

AABABBA

left	right	counts	right - left - maxCounts	> k
0	1	A : 1	-1	false
	2	A : 2	2-0-2 = 0	false
	3	A : 2, B : 1	3 - 0 - 2 = 1	false
	4	A : 3, B : 1	4 - 0 - 3 = 1	false
	5	A : 3, B : 2	5 - 0 - 3 = 2	true
1	5	A : 2, B : 2
1	6	A : 2, B : 3	6 - 1 - 3 = 2	true
2	6	A : 1, B : 3
2	7	A : 2, B : 3	7 - 2 - 3 = 2	true
3	7	A : 2, B : 2

left = 3 으로 끝

public int characterReplacement(String s, int k) {

        int left = 0;
        Map<Character, Integer> counts = new HashMap<>();
        for (int right = 1; right <= s.length(); right++) {
            counts.put(s.charAt(right - 1), counts.getOrDefault(s.charAt(right - 1),0)+1);

            int maxCharCount = Collections.max(counts.values());

            if (right - left - maxCharCount > k) {
                counts.put(s.charAt(left), counts.getOrDefault(s.charAt(left), 0) - 1);
                left++;
            }
        }
        return s.length() - left;
    }