박종훈 알고리즘 블로그

(Leetcode) 424 - Longest Repeating Character Replacement

New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time

위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.


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

내가 작성한 풀이

class Solution {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int i = 0;
        int j = 0;
        int max = Integer.MIN_VALUE;
        int result = Integer.MIN_VALUE;
        while (i < s.length()) {
            int index = s.charAt(i) - 'A';
            count[index]++;
            max = Math.max(max, count[index]);

            if (i - j - max + 1 > k) {
                count[s.charAt(j) - 'A']--;
                j++;
            }

            result = Math.max(result, i - j + 1);
            i++;
        }
        return result;
    }
}

나에게는 꽤 어려운 문제였다.

일종의 window 를 도입하여 해결한다.

  • 각 step마다 i 를 1씩 증가시킨다.
  • max : i와 j 사이의 가장 큰 연속된 char의 수.
  • i - j - max + 1 > k : 현재 부분 문자열의 길이에서 가장 많이 등장한 문자의 수를 뺀 값이 허용된 치환 횟수 k를 초과하는지 확인
    • 초과하였다면 j 를 1 증가시킨다.
  • 각 step마다 result 값을 계산하고 기존의 result 보다 큰 값이면 갱신한다.

TC, SC

시간 복잡도는 O(n)이고, 공간 복잡도는 O(1)이다.