76. Minimum Window Substring

76. Minimum Window Substring

 

https://youtu.be/jSto0O4AJbM?si=c41FJz9HSse3yfzE

 

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not t or not s:  # 예외 처리: t나 s가 비어있는 경우
            return ""

        countT = Counter(t)  # t의 각 문자의 빈도수
        window = {}  # 현재 윈도우 내 문자의 빈도수

        have, need = 0, len(countT)  # need는 t의 고유 문자 수
        res, resLen = [-1, -1], float("inf")  # 결과 저장 변수
        l = 0  # 왼쪽 포인터 초기화

        # 오른쪽 포인터로 윈도우 확장
        for r in range(len(s)):
            c = s[r]
            window[c] = 1 + window.get(c, 0)  # 현재 문자를 윈도우에 추가

            # 현재 문자가 countT에 있고, 필요 개수를 만족하면 have 증가
            if c in countT and window[c] == countT[c]:
                have += 1

            # 윈도우가 조건을 만족하면 왼쪽 포인터로 축소 시작
            while have == need:
                # 결과 업데이트
                if (r - l + 1) < resLen:
                    res = [l, r]
                    resLen = (r - l + 1)

                if s[l] in window:
                    # 윈도우의 왼쪽 문자 제거
                    window[s[l]] -= 1
                    
                if s[l] in countT and window[s[l]] < countT[s[l]]:
                    have -= 1  # 필요한 문자가 더 이상 만족되지 않으면 have 감소
                l += 1  # 왼쪽 포인터 이동

        # 결과가 초기값이면 조건을 만족하는 윈도우가 없음
        l, r = res
        return s[l:r + 1] if resLen != float("inf") else ""