[LeetCode] 424. Longest Repeating Character Replacement

임혁진·2022년 8월 15일

알고리즘

목록 보기

7/64

424. Longest Repeating Character Replacement

문제링크: https://leetcode.com/problems/longest-repeating-character-replacement/

문자열이 들어있는 스트링과 문자 교체 허용 수 k가 주어진다.
k만큼의 문자를 교체 해 만들 수 있는 연속된 같은 문자의 길이의 최댓값을 찾는다.

Solution 1

Sliding Window

조건에 맞는 연속된 문자열을 찾는 문제는 시작과 끝 인덱스를 기준으로 잡고 sliding window로 푸는 것이 좋을 것 같다. 이유는 일정한 인터벌에서 조건이 맞지 않으면 더 큰 사이즈로 키워도 조건에 부합하지 않기 때문에 경우의 수를 전부 탐색하지 않고도 불가능한 경우를 처리할 수 있다.
sliding window는 끝 인덱스를 키우면서 조건이 맞는지 확인하고 조건이 맞지 않으면 만족할 때까지 시작 인덱스를 키우면서 사이즈를 조절한다. 이 과정을 통해 불가능한 경우의 수를 빠르게 제거할 수 있다.

Alogrithm

start와 end 인덱스를 기준으로 하고 구간 내의 원소를 count하는 interval 맵을 만든다.
start 와 end를 0 에서 시작으로 end를 1씩 증가 시키며 구간의 크기를 키운다
구간에 맞는 조건은 구간의 길이 - 가장 많은 문자개수 <= k 이다.
조건에 맞을 경우 maxLength 값을 갱신시킨다.
조건에 맞지 않을 경우 start를 증가시킨다.
모든 문자열을 순회하고 end가 다다르면 maxLength를 반환한다.

var characterReplacement = function(s, k) {
    // start, end point로 슬라이딩
    // end point 기준으로 최고의 start point를 찾아가는 과정
    // 조건: 전체길이 - 가장많은원소(max of map.values)가 k와 작거나 같음
    
    let start = 0, end = -1;
    let maxLength = 0;
    const internal = new Map(); // 현재 internal에 포함된 값들
    
    // internal에 추가
    const insertToInternal = (val) => {
        internal.has(val) ? internal.set(val, internal.get(val) + 1) : internal.set(val, 1);
    }
    
    // internal에서 제거
    const removeFromInternal = (val) => {
        if (!internal.has(val)) return;
        internal.get(val) === 1 ? internal.delete(val) : internal.set(val, internal.get(val) - 1);
    }
    
    // 조건에 부합한지 확인
    const isPossible = () => (end - start + 1 - Math.max(...internal.values()) <= k);
    
  	// Iteration Start
    while (++end < s.length) {
        insertToInternal(s[end]);
        while (!isPossible()) {
            removeFromInternal(s[start++]);     
        }
        // console.log(start, end, internal);
        maxLength = Math.max(maxLength, end - start + 1);
    }
    return maxLength;
};

Solution 2

Sliding Window & maxCharCount

앞선 방법에서 최대 길이의 문자열을 계산할 때 interval의 맵을 매번 확인했다. 이번엔 새 문자를 삽입할 때만 maxCharCount가 증가할 수 있다는 성질을 이용해 해당 부분을 최적화 시켰다.

Algorithm

이전 방법과 Sliding Window는 동일하며 insertToInternal에서 maxCharCount를 갱신한다.

var characterReplacement = function(s, k) {
    // start, end point로 슬라이딩
    // end point 기준으로 최고의 start point를 찾아가는 과정
    // 조건: 전체길이 - 가장많은원소(max of map.values)가 k와 작거나 같음
    
    let start = 0, end = 0;
    let maxLength = 0;
    let maxCharCount = 0; // 추가한 부분
    const internal = new Map(); // 현재 internal에 포함된 값들
    
    // internal에 추가
    const insertToInternal = (val) => {
        internal.has(val) ? internal.set(val, internal.get(val) + 1) : internal.set(val, 1);
        maxCharCount = Math.max(maxCharCount, internal.get(val)); // 추가한 부분
    }
    
    // internal에서 제거
    const removeFromInternal = (val) => {
        if (!internal.has(val)) return;
        internal.get(val) === 1 ? internal.delete(val) : internal.set(val, internal.get(val) - 1);
    }
    
    // 조건에 부합한지 확인
    const isPossible = () => (end - start + 1 - maxCharCount <= k);
    
  	// Iternation Start
    while (end < s.length) {
        insertToInternal(s[end]);
        while (!isPossible()) {
            removeFromInternal(s[start++]);     
        }
        // console.log(start, end, internal);
        maxLength = Math.max(maxLength, end - start + 1);
        ++end;
    }
    return maxLength;
};