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 ""

 

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

        need = Counter(t)
        window = defaultdict(int)

        mustHave = 0
        minLen = float("inf")
        res = []
        
        left = 0
        for right in range(len(s)):
            ch = s[right]
            window[ch] +=1

            # 해당 문자 ch가 t문자열에 있고, 윈도우 내에서 ch의 개수 == need 내에서 ch개수 같으면
            if ch in need and window[ch] == need[ch]:
                mustHave +=1

            while mustHave == len(need):
                # 우선 모든 조건 만족하므로, 최소길이 갱신
                if right-left+1 < minLen:
                    res = [left, right]
                    minLen = right-left+1

                # 이제 왼쪽 증가..
                # 왼쪽 증가하기전, 왼쪽 문자 관련된 것들 개수 감소
                window[s[left]] -=1
                if s[left] in need and window[s[left]] < need[s[left]]:
                    mustHave -=1
                # 왼쪽 증가
                left+=1
            
        if not res:
            return ""
        
        l, r = res
        return s[l:r+1]