76. Minimum Window Substring

1. Description

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

2. Example

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.

3. Solution

• Runtime: 63
• Time Complexity: O(N)
• 설명
  • t문자열이 빈 문자열인 경우 ""만 리턴한다.
  • countT,window 해시 테이블을 만든다.
  • t문자열의 문자들을 countT해시테이블에 넣는다.
    • 만약 값이 없다면 0+1=1로 초기화
    • 📌문자의 등장 횟수를 저장하는 일반적인 패턴
  • have: 현재 window에서 t의 문자를 만족하는 개수
  • need t에서 서로 다른 문자의 개수 (countT의 길이)
  • res: 최종적으로 찾은 최소 window의 시작과 끝 인덱스
  • resLen: 현재까지 찾은 최소 길이의 window의 길이 (초기값은 inf)
    • 📌float("inf")를 통해 무한대를 설정할 수 있다.
  • for문을 돌며 오른쪽 포인터r을 s문자열을 따라 이동하며 window 딕셔너리에 문자 개수를 저장
  • 현재 window에 있는 문자 c가 t에 있고, countT에서 요구한 개수와 같으면 have +=1
  • have == need: 현재 윈도우가 t의 모든 문자를 포함하는 경우에 while루프 실행
  • 만약 (r-l+1) < resLen이면 res에 l과r의 값을 저장해주고 resLen의 값을 r-l+1로 저장해준다.
  • 📌window의 크기를 줄여 최소 window를 찾아야한다.
    • window[s[l]] -= 1을 통해 window에 있는 제일 왼쪽 문자의 개수를 지운다.
    • 만약 s[l]이 countT에 있고 window[s[l]] < countT[s[l]]이 되면 have -= 1
      • 충족되는 문자가 s[l]에 있을 경우 지우게 되면서 have가 감소한다.
    • l의 값은 증가한다.
  • res에 저장된 인덱스로 최소 윈도우 문자열을 반환
  • 만약 return이 inf그대로라면, t를 포함하는 부분 문자열이 없는 경우니까 ""반환환

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if t == "":
            return ""
 
        countT, window = {}, {}
 
        for c in t:
            countT[c] = 1 + countT.get(c, 0)
 
        have, need = 0, len(countT)
        res, resLen = [-1,-1], float("inf")
        l = 0
 
        for r in range(len(s)):
            c = s[r]
 
            window[c] = 1 + window.get(c, 0)
 
            if c in countT and countT[c] == window[c]:
                have += 1
            
            while have == need:
                if (r - l + 1) < resLen:
                    res = [l,r]
                    resLen = r - l + 1
 
                window[s[l]] -= 1
 
                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("inf") else ""
            

• 📌sliding window는 해시테이블을 사용하여 푸는 문제가 많은 거 같다.
  • 비교하면서 풀어야 하는 경우가 대부분이다.

4. What I Learned

References

• ChatGPT