[LeetCode] 424. Longest Repeating Character Replacement - Java

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

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.

 

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.

 

Constraints:

• 1 <= s.length <= 105
• s consists of only uppercase English letters.
• 0 <= k <= s.length

---

풀이

풀이 과정

알파벳 대문자로만 이루이진 문자열 s와 바꿀수 있는 알파벳의 개수 k가 주어질 때 만들 수 있는 가장 긴 반복되는 문자열의 길이를 구하는 문제이다.

문자열을 범위를 늘려가며 탐색하여 범위내에서 가장 많이 사용된 알파벳이 무엇인지 구하고 범위에서 가장 많이 사용된 알파벳의 개수를 뺀 나머지, 즉 바꿔야할 알파벳의 개수가 k보다 큰 지 비교한다. 
k보다 작거나 같다면 탐색 범위의 종료지점을 증가시켜 탐색하고, 크다면 시작 지점과 종료 지점을 같이 증가시켜 최대 길이를 유지한채 탐색 범위를 이동한다.

우선 탐색 범위내에서 사용된 알파벳의 개수를 카운팅하기 위해 알파벳의 개수 만큼의 배열을 생성한다.

// 알파벳의 개수를 카운팅할 배열
int[] alphabet = new int[26];

 

사용된 알파벳 중 가장 많이 사용된 알파벳의 개수를 구하기 위한 함수도 하나 아래와 같이 생성한다.

// 현재 탐색중인 범위내에서 가장 많이 사용된 알파벳의 개수를 반환
public int mostFreqVal() {
    int result = 0;

    for(int i : alphabet) {
        result = Math.max(result, i);
    }

    return result;
}

 

탐색 범위 내 가장 많이 나온 알파벳 개수를 저장할 변수와 탐색 시작지점 변수를 생성하고, 문자열 s의 첫 번째 알파벳의 개수를 증가시킨 상태로 탐색을 시작한다.

// 탐색 범위 내 가장 많이 나온 문자 개수
int max = 0;
// 첫 번째 문자 개수를 증가
alphabet[s.charAt(0) - 'A']++;
// 탐색중인 문자 범위의 왼쪽 인덱스값
int left = 0;

 

두 번째 문자부터 시작하여 문자열 s의 길이만큼 반복하여 탐색한다.
현재 탐색중인 문자의 사용 개수를 1 증가시키고 가장 많이 사용된 알파벳의 개수 max를 구한다.
이때 현재 탐색중인 범위에서 max를 뺀 개수, 즉 바꿔야할 알파벳의 개수가 k보다 큰 경우 왼쪽 인덱스에 해당하는 알파벳의 사용개수는 감소시키고 왼쪽 인덱스를 증가시킨다.

// 두 번째 문자부터 문자열의 길이만큼 탐색
for(int i = 1; i < s.length(); i++) {
    // 현재 탐색중인 문자의 사용 개수 증가
    alphabet[s.charAt(i) - 'A']++;
    max = mostFreqVal();

    // 현재 탐색중인 범위에서 가장 많이 사용된 알파벳을 뺀 개수,
    // 즉 바꿔야할 알파벳의 개수가 k보다 큰 경우
    if(i - left + 1 - max > k) {
        // 왼쪽 인덱스에 해당하는 알파벳 사용 개수를 감소
        alphabet[s.charAt(left) - 'A']--;
        // 탐색할 왼쪽 인덱스를 증가시킴
        left++;
    }
}

 

문자열의 길이에서 왼쪽 인덱스를 뺀 길이를 최종 return 한다.
이 때 해당 범위의 문자열이 가장 긴 반복된 문자열은 아니며 단순히 길이만을 알 수 있다.

// 문자열의 길이에서 왼쪽 인덱스를 뺀 값을 return
return s.length() - left;

---

최종 코드

class Solution {
    // 알파벳의 개수를 카운팅할 배열
    int[] alphabet = new int[26];

    public int characterReplacement(String s, int k) {
        // 탐색 범위 내 가장 많이 나온 문자 개수
        int max = 0;
        // 첫 번째 문자 개수를 증가
        alphabet[s.charAt(0) - 'A']++;
        // 탐색중인 문자 범위의 왼쪽 인덱스값
        int left = 0;
        
        // 두 번째 문자부터 문자열의 길이만큼 탐색
        for(int i = 1; i < s.length(); i++) {
            // 현재 탐색중인 문자의 사용 개수 증가
            alphabet[s.charAt(i) - 'A']++;
            max = mostFreqVal();
            
            // 현재 탐색중인 범위에서 가장 많이 사용된 알파벳을 뺀 개수,
            // 즉 바꿔야할 알파벳의 개수가 k보다 큰 경우
            if(i - left + 1 - max > k) {
                // 왼쪽 인덱스에 해당하는 알파벳 사용 개수를 감소
                alphabet[s.charAt(left) - 'A']--;
                // 탐색할 왼쪽 인덱스를 증가시킴
                left++;
            }
        }
        
        // 문자열의 길이에서 왼쪽 인덱스를 뺀 값을 return
        return s.length() - left;
    }

    // 현재 탐색중인 범위내에서 가장 많이 사용된 알파벳의 개수를 반환
    public int mostFreqVal() {
        int result = 0;
        
        for(int i : alphabet) {
            result = Math.max(result, i);
        }
        
        return result;
    }
}

---