LeetCode Longest Repeat 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.

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

Example 1:

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

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.

어우 영어다 영어
이번 문제는 짧게 요약해보자면 대문자 알파벳으로 구성된 문자열 s와 정수형 k가 주어지는데, 이때 k번의 알파벳 대체가 가능하다.
이 경우 가능한 가장 긴 연속되는 문자열의 크기를 찾는것!

일단 문제를 읽고 어떻게 풀어야 할지 계속 고민해봤는데 답이 안나왔다..
모든 알파벳을 가지고 있는 배열에 처음 위치와 마지막 위치, 그리고 단어 사이의 간격을 저장해서 해볼까 라는 생각을 했지만... 실패했다..

그래도 생각해본 2가지의 경우는
k = s.length() k = s.length() - 1 일 때 굳이 검사를 하지 않아도 모든걸 대체하거나 알파벳 하나 제외하고 대체하면 되니까 바로 s.length()를 반환하면 될 것 같다는 생각이었다.

근데 나중에 이거 빼고 시간 비교해봤는데 큰 차이는 없었음..ㅠㅠ

아무튼 코드를 보자..

public int charcaterReplacement(String s, int k) {
        int length = s.length();
        int max = 0;

        for (char c = 'A'; c <= 'Z'; c++) {
            int i = 0, j = 0, replaced = 0;
            while(j < length) {
                if (k >= length - 1) {  // k가 최대 길이와 같거나 하나 작으면 최대 길이와 같음
                    return length;
                } else if(s.charAt(j) == c){ // 같으면 길이를 하나 증가
                    j++;
                } else if (replaced < k){     // 대체가 k보다 작으면 하나씩 올림
                    j++;
                    replaced++;
                } else if (s.charAt(i) == c){     // 위의 케이스가 아니라면 시작부분 인덱스부터 증가
                    i++;
                } else {		// 전부 아니라면 대체 문자수 조정
                    i++;
                    replaced--;
                }
                max = Math.max(max, j -1);
            }
        }

        return max;
    }
    

이렇게 했는데 사실 다른 사람의 코드를 참고 했다..

이 방식은 슬라이딩 윈도우라는 알고리즘 방식이라고 한다!!
투포인터 방식을 기본으로 left와 right를 움직이는 방식

주석에 달아놓은 것처럼 같으면 그대로 증가, 다른데 replaced가 남아있으면 대체, 그것도 아니고 시작근처가 같다고 하나 증가하고 모두 아니라면 시작 근처를 대체하고 증가하는 계속해서 조정해주는 방식이라고 한다!!

아 알고리즘 어렵다;;