[LeetCode] 76. Minimum Window Substring

https://leetcode.com/

Given two strings s and t of lengths m and n respectively, return the minimum window 
substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

 

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

 

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints:

• m == s.length
• n == t.length
• 1 <= m, n <= 10^5
• s and t consist of uppercase and lowercase English letters.

Code:

function minWindow(s, t) {
    // 각 문자의 등장 횟수를 저장하는 객체
    const charCount = {};
    // 타겟 문자열 t의 각 문자 등장 횟수를 기록
    for (const char of t) {
        charCount[char] = (charCount[char] || 0) + 1;
    }
    // 필요한 문자의 총 개수
    let requiredChars = Object.keys(charCount).length;
    // 윈도우의 시작과 끝 인덱스
    let left = 0;
    let right = 0;
    // 최소 윈도우의 길이와 시작 인덱스
    let minLength = Infinity;
    let minWindowStart = 0;
    // 남은 필요한 문자의 개수
    let missingChars = 0;
    // 문자열을 검사하는 동안의 반복문
    while (right < s.length) {
        const char = s[right];
        // 현재 문자가 필요한 문자에 속하는 경우
        if (charCount[char] !== undefined) {
            charCount[char]--;
            // 필요한 문자를 다 찾은 경우
            if (charCount[char] === 0) {
                missingChars++;
            }
        }
        // 모든 필요한 문자를 찾은 경우
        while (missingChars === requiredChars) {
            // 현재 윈도우의 길이가 최소인지 확인
            if (right - left + 1 < minLength) {
                minLength = right - left + 1;
                minWindowStart = left;
            }
            const leftChar = s[left];
            // 윈도우의 왼쪽을 이동하면서 필요한 문자를 찾음
            if (charCount[leftChar] !== undefined) {
                charCount[leftChar]++;

                // 필요한 문자를 놓친 경우
                if (charCount[leftChar] > 0) {
                    missingChars--;
                }
            }
            left++;
        }
        // 오른쪽으로 계속 확장
        right++;
    }
    // 최소 윈도우를 찾은 경우 반환, 그렇지 않으면 빈 문자열 반환
    return minLength === Infinity ? "" : s.substr(minWindowStart, minLength);
}

 

Solutions Code :

var minWindow = function(s, t) {
    // 만약 t의 길이가 s의 길이보다 크다면 빈 문자열 반환
    if (t.length > s.length) return '';
    // 필요한 문자의 개수를 저장하는 객체
    const neededChars = {};
    // t 문자열의 각 문자의 등장 횟수를 기록
    for (let char of t) {
        neededChars[char] = (neededChars[char] || 0) + 1;
    }
    // 윈도우의 왼쪽, 오른쪽 포인터 및 필요한 문자의 종류 수 초기화
    let left = 0;
    let right = 0;
    let neededLength = Object.keys(neededChars).length;
    // 결과로 반환할 최소 윈도우의 부분 문자열
    let substring = '';
    // 오른쪽 포인터를 이동하면서 탐색
    while (right < s.length) {
        const rightChar = s[right];
        // 현재 문자의 필요한 개수를 감소하고, 필요한 문자 종류 수 업데이트
        neededChars[rightChar]--;
        if (neededChars[rightChar] === 0) neededLength--;
        // 모든 필요한 문자를 찾은 경우
        while (neededLength === 0) {
            // 현재까지의 부분 문자열이 더 작거나 처음인 경우 갱신
            if (!substring || substring.length > right - left + 1) {
                substring = s.slice(left, right + 1);
            }
            const leftChar = s[left];
            // leftChar가 필요한 개수가 0이 되면, 다시 필요한 문자로 카운트
            if (neededChars[leftChar] === 0) {
                neededLength++;
            }
            // leftChar의 필요한 개수를 증가시키고, 왼쪽 포인터 이동
            neededChars[leftChar]++;
            left++;
        }
        // 오른쪽 포인터 이동
        right++;
    }
    // 최소 윈도우 부분 문자열 반환
    return substring;
};

 

출처 : https://leetcode.com/problemset/all/