[LeetCode] 424. Longest Repeating Character Replacement

424. Longest Repeating Character Replacement

LeetCode

 

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.
Return the length of the longest substring containing the same letter you can get after performing the above operations.

문자열 s와 정수 k가 주어집니다. 문자열 내에서 임의의 문자를 선택해 다른 영문 대문자로 변경하는 조작을 최대 k번 수행할 수 있습니다.
이러한 조작을 거친 후 얻을 수 있는, 같은 문자로만 이루어진 가장 긴 부분 문자열(substring)의 길이를 반환하세요.

 

Example

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4. There may exists other ways to achieve this answer too.

---

1. 문제 요구사항 분석

같은 문자로만 이루어진 가장 긴 부분 문자열의 길이 구하기

 

2. 접근 전략

슬라이딩 윈도우 이용하기 !

슬라이딩 윈도우 : 고정된 크기 또는 가변적인 크기의 창문을 하나 만들어두고, 이를 오른쪽으로 한 칸씩 이동시키면서 창문 안에 있는 데이터만 처리

class Solution {
    public int characterReplacement(String s, int k) {
        int[] alpCount = new int[26]; // 알파벳 갯수
        int left = 0;
        int maxCount = 0;
        int maxLength = 0;

        for (int right = 0; right < s.length(); right++) {
            // 현재 문자 개수 증가
            maxCount = Math.max(maxCount, ++alpCount[s.charAt(right) - 'A']);

            // 바꿔야 할 문자의 개수(전체 길이 - 최다 빈도수)가 k를 초과하면
            if (right - left + 1 - maxCount > k) {
                alpCount[s.charAt(left) - 'A']--;
                left++; // 왼쪽 포인터 이동 (윈도우 유지)
            }

            // 최댓값 갱신
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}