[Leetcode] 76. Minimum Window Substring - JS

https://leetcode.com/problems/minimum-window-substring/description/?envType=study-plan-v2&envId=top-interview-150

 

 

 

1. 문제 분석

문제분석
--------------------
문자열 s, t와 이들의 길이 m, n이 각각 주어진다.
중복을 포함한 t 안의 모든 문자가 s의 부분 문자열이 되는 최소 window를 반환하라.
부분 문자열이 없다면 빈 문자열을 반환하라.

제한조건
--------------------
- m == s.length
- n == t.length
- 1 <= m, n <= 10^5
- s와 t는 대소문자로 구성된 영문자이다.

 

2. 접근 방법

접근방법 - Sliding Window + Hash Table
--------------------
t 문자열의 hash table을 만들고 start, end 포인터로 window 크기를 구하여 
점차 window 크기를 점차 줄여나가는 방향으로 접근한다.

- tHash: t 문자열의 hash
- sHash: s 문자열의 hash
- required: 필요한 고유 문자 갯수
- start, end: Sliding window 포인터
- minStart: 최소길이 부분 문자열 시작 포인터
- minLen: 부분 문자열 최소 길이
- matches: sHash의 빈도수와 tHash의 빈도수가 동일한 문자의 갯수
-> t에서 필요한 문자 수만큼 채운 경우 matches 증가


1. hash 생성
우선, t의 hash table을 만들어 필요한 고유 문자 수를 카운팅한다.
고유 문자수를 카운팅하는 이유는 t 문자들이 window 내에 모두 포함될 때 증가하는 matches 변수와 비교하여
이 후에 sliding window 크기를 줄이기 위한 조건으로 사용하기 위함이다.

2. sliding window 탐색
- end 포인터가 s 문자열 끝에 도달할 때 까지 반복하여 sliding window를 탐색한다.
- tHash에 존재하는 문자일 경우, sHash에 빈도수를 추가
- sHash 빈도수와 tHash 빈도수가 동일할 경우 matches를 증가시킨다.

3. window 크기 줄이기 ⭐️
matches와 required가 동일한 경우엔 이미 t 문자열이 window에 모두 포함되어 있는 상태이므로
이 때는 start, end 포인터를 비교하여 최소길이를 업데이트하고 
최소길이를 갖는 부분문자열의 시작 포인터도 업데이트한다.

sHash의 빈도수를 줄여주고 sHash 빈도수가 tHash 보다 작으면 
t 문자열을 모두 포함하고 있는 것이 아니므로 matches를 감소시킨다.
이 후 start 포인터를 이동시킨다.

 

Key Point는 matches === required 가 만족하면 반복해서 start 포인터를 이동시켜

window 크기의 최솟길이와 그 때의 부분 문자열 시작 포인터를 구하는 것이다.

 

 

3. 코드

var minWindow = function(s, t) {
    let tHash = {};
    let sHash = {};
    let required = 0;
    let start = 0, end = 0, minStart = 0, minLen = Infinity, matches = 0;
    
    // t의 문자를 해시맵에 저장
    for (let char of t) {
        if (tHash[char]) {
            tHash[char]++;
        } else {
            tHash[char] = 1;
            required++;  // 필요한 고유 문자 수 증가
        }
    }

    // 슬라이딩 윈도우 탐색
    while (end < s.length) {
        let endChar = s[end];

        // end 포인터가 가리키는 문자가 tHash에 있으면 카운팅
        if (tHash[endChar]) {
            if (!sHash[endChar]) sHash[endChar] = 0;
            sHash[endChar]++;
            
            // t에서 필요한 문자 수만큼 채운 경우 matches 증가
            if (sHash[endChar] === tHash[endChar]) {
                matches++;
            }
        }

        // 모든 t의 문자가 포함된 경우
        while (matches === required) {
            // 최소 길이 업데이트
            if (end - start + 1 < minLen) {
                minLen = end - start + 1;
                minStart = start;
            }

            let startChar = s[start];

            // start 포인터가 가리키는 문자가 tHash에 있으면 카운팅 감소
            if (tHash[startChar]) {
                sHash[startChar]--;
                if (sHash[startChar] < tHash[startChar]) {
                    matches--;  // t의 문자가 더 이상 충분히 포함되지 않음
                }
            }
            
            start++;  // 윈도우를 최소화하기 위해 start 이동
        }

        end++;  // 윈도우 확장을 위해 end 이동
    }

    // 결과 반환: 최소 윈도우 길이가 갱신된 적이 있으면 해당 부분 문자열, 아니면 빈 문자열
    return minLen === Infinity ? "" : s.slice(minStart, minStart + minLen);
};

 

 

4. 복잡도 분석

- 시간복잡도: O(m), m은 s 문자열의 길이

- 공간복잡도: O(1)

 

sliding window, hash table 방법으로 시도했다. 하지만 내 방법으론 단순히 tHash, sHash의 빈도수 대소비교를 하여 최소의 window 길이를 구하기에는 적절하지 않았다. GPT에게 나의 코드를 질문하여 내 코드를 기반으로 최적의 코드를 얻어내었다.

 

window를 탐색 시에는 end 포인터는 window 크기 증가 즉, t의 모든 문자를 포함할 때 까지 증가시키는 방식으로 고정한다.

이 후 start 포인터를 움직여 window 크기를 최소화한다.

 

5.  이해하기 좀 더 쉬운 풀이 feat. Claude

Claude AI에게 물어보며 좀 더 이해하기 쉬운 코드로 풀어봤다.

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    // t의 문자별 필요한 개수를 저장
    const need = {};
    for (let char of t) {
        need[char] = (need[char] || 0) + 1;
    }
    
    // 필요한 unique 문자의 개수
    const requiredChars = Object.keys(need).length;
    
    // 현재 윈도우에서 조건을 만족하는 문자의 개수
    let matches = 0;
    
    // 현재 윈도우의 문자 개수를 저장
    const window = {};
    
    // 결과 변수들
    let left = 0; // s 문자열 시작 포인터
    let right = 0; // s 문자열 끝 포인터
    let minLen = Infinity;
    let minLeft = 0; // 최소 부분 문자열 시작 포인터

    while (right < s.length) {
        const char = s[right];
        window[char] = (window[char] || 0) + 1

        // window에 꼭 필수적인 문자의 갯수가 동일할 때만 matches 추가
        if (need[char] && window[char] === need[char]) {
            matches++;
        }

        while (matches === requiredChars) {
            // 현재 부분 window의 길이 갱신
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minLeft = left;
            }

            const leftChar = s[left];
            window[leftChar]--;

            if (need[leftChar] && window[leftChar] < need[leftChar]) {
                matches--;
            }
            left++;
        }
        right++;
    }
    return minLen === Infinity ? '' : s.slice(minLeft, minLeft + minLen)
};

 

window를 hash로 구현하여 갯수를 담았다.

window의 시작 포인터, 종료 포인터 그리고 최소 부분 문자열의 시작 포인터를 정하여

t 문자열의 유니크한 문자의 갯수와 window에 포함된 유니크 갯수가 동일할 때,

window의 시작 포인터를 이동하면서 window의 최소 길이를 갱신해줬다.

 

기존에 풀던 방식이랑 얼추 비슷한데, 변수명을 정확히 설정하고 이해하니 더 가독성이 향상된 코드가 되었다.