LeetCode (C/C++, Java) 424. Longest Repeating Character Replacement

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

---

풀이

투 포인터임은 알았는데, 세부 조건을 모르겠어서 답지를 봤다.
현재 범위에서 가장 많은 알파벳 수를 저장한 후, 해당 범위에서 그 알파벳을 제외한 다른 알파벳의 개수가 k개가 넘을 때, k개를 만족시킬 때까지 범위를 조정한다.

---

C/C++ 코드

class Solution {
public:
    int characterReplacement(string s, int k) {
        int l = 0, maxLen = 0, maxAlphaCount = 0;
        int alpha[26] = {0, };

        for (int r = 0; r < s.size(); r++) {
            alpha[s[r] - 'A']++;

            // 현재 범위에서 가장 많은 알파벳 개수 저장
            maxAlphaCount = max(maxAlphaCount, alpha[s[r] - 'A']);

            // maxAlphaCount를 제외하고 다른 문자가 범위 내에 k개 이상 있을 때 범위 조절
            while ((r - l + 1) - maxAlphaCount > k) {
                alpha[s[l] - 'A']--;
                l++;
            }

            // 최대 범위 갱신
            maxLen = max(maxLen, r - l + 1);
        }
        return maxLen;
    }
};

 

Java 코드

class Solution {
    public int characterReplacement(String s, int k) {
        int l = 0, len = s.length();
        int maxLen = 0, maxAlphaCount = 0;
        
        int[] alpha = new int[26];
        for (int r = 0; r < len; r++) {
            alpha[s.charAt(r) - 'A']++;

            // 현재 범위에서 가장 많은 알파벳 개수 저장
            maxAlphaCount = Math.max(maxAlphaCount, alpha[s.charAt(r) - 'A']);

            // maxAlphaCount를 제외하고 다른 문자가 범위 내에 k개 이상 있을 때 범위 조절
            while ((r - l + 1) - maxAlphaCount > k) {
                alpha[s.charAt(l) - 'A']--;
                l++;
            }

            // 최대 범위 갱신
            maxLen = Math.max(maxLen, r - l + 1);
        }
        return maxLen;
    }
}