[DSA][Sliding Window] 04. Minimum Window Substring

LeetCode 76

 

 04. Minimum Window Substring

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.

 

 

[질문하기]

- 문자 비교는 대소문자를 구분하나요? YES

- 항상 valid 한 정답이 있나요? NO

- 최소 윈도우가 여러 개일 수 있는 경우, 어떤 것을 반환하나요? UNIQUE 함

 

 

[아이디어]

- hashmap을 통해 특정 문자가 포함되는지 체크하고, 변수를 통해 모든 문자가 포함되었는지 체크하자.

 

 

[풀이 1] Sliding Window

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if len(s) < len(t):
            return ""
        
        countMapS, countMapT = {}, {}

        for c in t:
            countMapT[c] = 1 + countMapT.get(c, 0)

        l = 0
        have, need = 0, len(countMapT)
        res, minLen = [-1, -1], 1e9
        for r in range(len(s)):
            countMapS[s[r]] = 1 + countMapS.get(s[r], 0)

            if s[r] in countMapT and countMapT[s[r]] == countMapS[s[r]]:
                have += 1
            
            while have == need:
                if (r - l + 1) < minLen:
                    res = [l, r]
                    minLen = r - l + 1
                
                countMapS[s[l]] -= 1
                if s[l] in countMapT and countMapS[s[l]] < countMapT[s[l]]:
                    have -= 1
                l += 1
            
        l, r = res
        return s[l:r+1] if minLen != -1 else ""

앞서 풀었던 Permutation in String 문제에서는, 2025.06.09 - [자료구조와 알고리즘] - [DSA][Sliding Window] 03. Permutation in String 한 문자열이 한 문자열의 permutation을 포함하고 있는지를 확인했다. 우리는 두 문자열의 문자 빈도수 (frequency count)를 비교하는 방식으로, 하나가 다른 하나의 순열(permutation) 임을 확인했다.

하지만 이번 문제에서는, 단순히 permutation이 아니라, 위치를 고려하지 않고 t의 모든 문자를 포함한 최소 부분 문자열을 찾는 문제라는 차이가 있다.

 

문제 예시에서처럼 s="ADOBECODEBANC", t="ABC"라면 우리는 다음과 같이 체크할 수 있다는 것을 안다.

Sliding Window를 사용해서 우측 포인터 R을 확장하며 현재 윈도우에 문자를 하나씩 추가하고 윈도우에 t의 문자가 충분히 들어왔다면, 좌측 포인터 L을 줄여서 윈도우를 가능한 한 줄인다. 이런 방식을 반복하여 현재 윈도우가 조건을 만족할 때마다 최소 길이 후보를 갱신한다.

 

그렇다면, "윈도우에 t의 문자가 충분히 들어왔는지"를 어떻게 체크할까?

먼저, t의 각 문자의 개수를 카운트한 countMapT을 만든다. 그리고 윈도우를 확장하면서 s의 문자를 카운트하는 countMapS를 만들고 countMapT의 각 KEY에 대해 countMapS  해당 문자가 같거나 더 많이 포함되었을 때, 해당 문자가 충분히 포함된 것으로 간주할 수 있다.

 

이때, 매번 윈도우를 확장할 때마다 countMapT의 모든 KEY에 대해 확인하는 것이 아니라, 지금 확장한 윈도우의 글자가 t에 포함되는 문자라면 해당 문자가 충분히 포함되어 있는지 체크하고 (countMapS에 저장된 개수가 더 많은지) have 변수를 1만큼 증가한다. "이 문자는 가지고 있다, 조건을 충족했다"라는 의미로, 이 have 변수가 countMapT의 KEY 개수와 같아지면 모든 문자를 충분히 가지고 있다는 의미가 되므로 윈도우에 t의 모든 문자가 충분히 들어있는지를 체크할 수 있다.

 

⏱️ 시간복잡도

t, s 문자열을 한 번 순회하기 때문에 O(n + m)의 시간 복잡도를 갖는다. (n, m은 각 문자열의 길이)

🧠 공간복잡도

최악의 경우 두 map을 모두 저장해야 하기 때문에 O(n + m)의 복잡도를 갖지만 (그중 unique 한 개수), 저장하는 알파벳의 개수가 유한하기 때문에 O(1)로 볼 수도 있다.