[LeetCode] 76. Minimum Window Substring

https://leetcode.com/problems/minimum-window-substring/

Minimum Window Substring - LeetCode

t의 문자들이 속해있는 가장 최소 문자열을 찾는 문제이다.

• t 안의 각 문자 당 문자 개수를 센다. (count 초기화)
• 한 개 문자의 count 조건을 만족하면(window[c] == countT[c]) have 증가
• have == need 라면
  • 최소길이 결과 업데이트
  • 맨 왼쪽문자 pop (문자길이 줄여가기 위함)
  • count조건 만족x라면 have 감소
  • L pointer 증가

•  

---

SOLUTION CODE

# PYTHON

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if t == "":
            return ""
        
        countT, window = {}, {}
        # countT initialize
        for c in t:
            countT[c] = 1 + countT.get(c, 0)
        
        have, need = 0, len(countT)
        res, resLen = [-1, -1], float("infinity")
        l = 0
        for r in range(len(s)):
            c = s[r] # 각 문자에 대해
            window[c] = 1 + window.get(c, 0) # count 증가

            # t안의 문자에 대해서만 비교 + count조건만족o
            if c in countT and window[c] == countT[c]:
                have += 1 # have 증가
            
            # 만약 같다면(조건 만족)
            while have == need:
                # 결과 업데이트
                if (r - l + 1) < resLen:
                    res = [l, r]
                    resLen = r - l + 1
                # pop from the left of our window
                window[s[l]] -= 1
                # t안의 문자 + count조건 만족X
                if s[l] in countT and window[s[l]] < countT[s[l]]:
                    have -= 1
                l += 1
        l, r = res
        return s[l : r + 1] if resLen != float("infinity") else ""