76. Minimum Window Substring (Hash Table, String, Sliding Window)

링크 - https://leetcode.com/problems/minimum-window-substring/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Hard

Intuition

이 문제는 sliding window를 사용하여 풀 수 있는 문제이다. 알고리즘은 다음과 같다.

1. 만약 t나 s가 valid string이 아니면, ""을 반환한다.

2. t의 counter를 만들고 counter의 길이만큼을 required변수에 넣는다. 이는 우리가 나중에 필요한 글자들이 채워질때 모든 필요한 글자들이 채워졌는지 확인할 때 쓰일 것이다.

3. s를 t의 글자만 가지도록 filtering한다. 각 원소는 글자와 원래 s에서의 인덱스를 가져야 할 것이다.

4. left와 right를 0으로 초기화 하고, required와 비교할 formed를 0으로 초기화 한다. 또한 글자 counter를 추적하기 위해 window_counter = {}를 만든다.

5. ans = float("inf"), None, None으로 tuple of the form (window length, left, right)로 추적할수 있게 초기화 한다.

6. r이 filtered_s길이만큼 되도록 while문을 돌릴것이다. 

6.1 먼저 r에 해당되는 글자를 window_counter채우고 t_counter를 통해 원하는 만큼의 글자가 채워지면 formed += 1한다.

6.2 formed == required가 되면, left를 오른쪽으로 움직이면서 최소 거리를 찾아야 한다. 먼저 left에 있는 글자를 빼온 뒤, 현재 길이를 구해서 이전 길이보다 작으면 ans를 업데이트한다. 그리고 매번 window_counter의 글자를 업데이트해서 만약 t_counter보다 작아지면 formed -= 1해준다.

7. ans[0] == float("inf")면 만족하는 글자가 없으므로 ""를 반환한다. 아니면 우리가 가지고 있는 left, right에 있는 인덱스로 정답을 반환한다.

Code

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t:
            return ""

        t_counter = Counter(t)
        required = len(t_counter)

        filtered_s = []
        for i, c in enumerate(s):
            if c in t_counter:
                filtered_s.append((c, i))

        formed = 0
        left, right = 0, 0
        window_counter = {}

        ans = float('inf'), None, None

        while right < len(filtered_s):
            c = filtered_s[right][0]

            window_counter[c] = window_counter.get(c, 0) + 1
            if window_counter[c] == t_counter[c]:
                formed += 1

            while left <= right and required == formed:
                c = filtered_s[left][0]

                start = filtered_s[left][1]
                end = filtered_s[right][1]
                if end - start + 1 < ans[0]:
                    ans = end - start + 1, start, end

                window_counter[c] -= 1
                if window_counter[c] < t_counter[c]:
                    formed -= 1

                left += 1

            right += 1

        return "" if ans[0] == float('inf') else s[ans[1]:ans[2]+1]

Complexity

S = length of string s, T = length of string t

Time Complexity: O(s + t) 여기서 우리는 filtered_s를 사용하였으므로 len(filtered_s) << S 일 경우, time complexity에서 큰 이득을 볼 수 있다. 

Space Complexity: O(s + t)