[LeetCode] 76. Minimum Window Substring

문체 출처: https://leetcode.com/problems/minimum-window-substring/

Minimum Window Substring - LeetCode

---

문제

길이 m과 n의 두 문자열 s와 t가 주어진다. 윈도우 내에 t의 문자(중복 포함)가 모두 포함되도록 s의 최소 운도우 부분 문자열을 반환하라. 만약 부분 문자열이 없다면, 빈 문자열인 ""을 반환하라.

 

테스트케이스에는 유일한 답이 존재한다.

 

부분 문자열은 문자열 안에서 문자의 연속적인 시퀀스를 말한다.

 

Follow up: O(m + n) 이내에 동작하는 알고리즘을 작성할 수 있는가? 

예제

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Input: s = "a", t = "a"
Output: "a"

Explanation: The entire string s is the minimum window.

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.

---

풀이

처음에 O(m + n)이라는 조항에 구애받지 않고 문제를 풀려고 접근을 하였고, 이에 이진 탐색(Binary Search)을 사용하여 문제에 접근하였다. 이때 이진탐색의 대상은 윈도우의 사이즈이다.

 

찾아야 하는 하위 문자열의 길이(l)를 생각해보면, 최소 t 와 같은 크기이거나 최대 s 자신의 크기일 것이다(n ≤ l ＜ m). 이를 이용하여 다음과 같이 이진탐색의 코드 구조를 만들 수 있다.

var minWindow = function(s, t) {
    const m = s.length;
    const n = t.length;
    if (m < n) { return ""; }
    
    // tmap: t의 구성 문자를 카운트하는 맵 변수
    // 하위 문자열에 t 의 모든 문자가 들어있는지 확인 용도
    const tLetters = new Map();
    t.split('').forEach(char => {
        if (!tLetters.has(char)) { tLetters.set(char, 0); }
        tLetters.set(char, tLetters.get(char) + 1);
    });
    
    // 본격적인 이진탐색 알고리즘
    let ans = "";
    let lo = n, hi = m;
    while (lo <= hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        
        // findSubstr(): mid크기의 윈도우에 t의 문자가 모두 존재할 수 있는지 확인하는 함수
        // - 존재할 수 있다면, 해당 하위 문자열을 반환
        // - 존재하지 않는다면, 빈 문자열 ""을 반환
        const tmp = findSubstr(s, new Map(tLetters), mid);
        if (tmp == '') {
            lo = mid + 1;
        } else {
            ans = tmp;
            hi = mid - 1;
        }
    }
    return ans;
};

위 코드에서 구현해야 하는 부분은 findSubstr() 함수 이다. findSubstr()함수는 mid 크기의 윈도우를 s에서 움직이면서 t의 문자를 모두 갖는 부분을 체크해 반환하는 함수로 다음과 같이 구현할 수 있다.

var findSubstr = function(s, tMap, windowSize) {
    // 초기 윈도우 설정
    for (let i = 0; i < windowSize; i++) {
        if (!tMap.has(s[i])) { continue; }
        tMap.set(s[i], tMap.get(s[i]) - 1 );
    }
   	
    if (checkWindow(tMap)) { return s.substring(0, windowSize); }
    
    // 윈도우를 움직이면서 t 문자열의 모든 문자를 갖는 곳이 있는지 체크
    for (let i = windowSize; i < s.length; i++) {
        if (tMap.has(s[i-windowSize])) { tMap.set(s[i-windowSize], tMap.get(s[i-windowSize]) + 1); }
        if (tMap.has(s[i])) { tMap.set(s[i], tMap.get(s[i]) - 1); }
        
        if (checkWindow(tMap)) { return s.substring(i-windowSize+1, i+1); }
    }
    
    return "";
}

var checkWindow = function(tMap) {
    for (let [_, v] of tMap) {
        if (v > 0) { return false; }
    }
    return true;
}

이 알고리즘의 시간 복잡도에 대해 생각해보자. 이진 탐색에서 O(logM), findSubStr()에서 O(M), 그리고 checkWindow() 에서 O(N)의 시간 복잡도를 갖을 것이기 때문에 전체 알고리즘은 O(N * M * logM)의 시간 복잡도를 갖는다.

 

Github: 76.js

GitHub - opwe37/Algorithm-Study