Day032 - 76. Minimum Window Substring

76. 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.

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 <= 105
• s and t consist of uppercase and lowercase English letters.

Follow up: Could you find an algorithm that runs in O(m + n) time?

내 풀이

from collections import defaultdict, Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if len(s) == len(t) and Counter(s) == Counter(t): return s
        if len(s) <= len(t): return ""
        if len(t) == 1 and t in s: return t

        t_dict = Counter(t)
        s_dict = defaultdict(int)

        need_count = len(t_dict)
        current_count = 0

        l, r = 0, 0
        min_len = float("inf")
        answer = []

        while r <= len(s)-1:
            r_str = s[r]
            s_dict[r_str] += 1

            # s_dict에 지금 r pointer가 가르키는 글자를 더해둔 상태.
            if r_str in t_dict and s_dict[r_str] == t_dict[r_str]:
                current_count += 1
                
            # current_count가 need_count와 같아지면 l을 오른쪽으로 옮기면서 need_count가 1 내려갈 때 까지 이동
            if current_count == need_count:
                if r-l+1 < min_len:
                    min_len = r-l+1
                    answer = [l, r+1]
                
                while current_count == need_count:
                    l_str = s[l]

                    if l_str in t_dict and s_dict[l_str] == t_dict[l_str]:
                        s_dict[l_str] -= 1
                        current_count -= 1
                        l += 1
                        break
                    else:
                        s_dict[l_str] -= 1
                        l += 1
                        if current_count == need_count and r-l+1 < min_len:
                            # print(f"if : {l}, {r}, min_len : {min_len}")
                            min_len = r-l+1
                            answer = [l, r+1]

            r += 1

        return s[answer[0]:answer[1]] if answer else ""

# Time Complexity : \(O(N)\)

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        dict_t = Counter(t)
        required = len(dict_t)

        # t 만 있는 s 로 만듬
        filtered_s = [(i, char) for i, char in enumerate(s) if char in dict_t]

        l = 0
        formed = 0
        window_counts = Counter()
        ans = float("inf"), None, None

        for r, (index, char) in enumerate(filtered_s):
            window_counts[char] += 1

            if window_counts[char] == dict_t[char]:
                formed += 1

            while l <= r and formed == required:
                char = filtered_s[l][1]

                end = filtered_s[r][0]
                start = filtered_s[l][0]
                if end - start + 1 < ans[0]:
                    ans = (end - start + 1, start, end)

                window_counts[char] -= 1
                if window_counts[char] < dict_t[char]:
                    formed -= 1
                l += 1

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