76. Minimum Window Substring

Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string "".

Note that If there is such a window, it is guaranteed that there will always be only one unique minimum window in s.

My Answer 1: Time Limit Exceeded (265 / 266 test cases passed.)

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if len(s) < len(t):
            return ""
        if s in t:
            return s
        if t in s:
            return t
        
        result = ""
        resultlen = len(s)  # minimum 찾기 위해서
        for i in range(len(s)):
            dic = {}
            if s[i] in t:
                dic[s[i]] = 1
                # temp 는 t 에서 찾은 문자들을 하나씩 제거해감
                # => temp 가 "" 이면 substring 인 것
                temp = t[:t.find(s[i])] + t[t.find(s[i])+1:]
                for j in range(i+1, len(s)):
                    if s[j] in temp:
                        dic[s[j]] = 1
                        temp = temp[:temp.find(s[j])] + temp[temp.find(s[j])+1:]
                    # substring 을 찾았으면 result update
                    if len(dic) == len(t) or len(temp) == 0:
                        if resultlen >= j-i+1:
                            resultlen = j-i+1
                            result = s[i:j+1]
                            break
        
        return result

t 에서 찾은 문자는 하나씩 지워가는 식으로 substring 을 찾아서 result 에 minimum 을 업데이트 함

하지만 타임리밋~~

Solution 1:

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t or len(s) < len(t):
            return ''
        
        t_counter = Counter(t)
        chars = len(t_counter.keys())
        
        s_counter = Counter()
        matches = 0
        
        answer = ''
        
        i = 0
        j = -1 # make j = -1 to start, so we can move it forward and put s[0] in s_counter in the extend phase 
        
        while i < len(s):
            
            # extend
            if matches < chars:
                
                # since we don't have enough matches and j is at the end of the string, we have no way to increase matches
                if j == len(s) - 1:
                    return answer
                
                j += 1
                s_counter[s[j]] += 1
                if t_counter[s[j]] > 0 and s_counter[s[j]] == t_counter[s[j]]:
                    matches += 1

            # contract
            else:
                s_counter[s[i]] -= 1
                if t_counter[s[i]] > 0 and s_counter[s[i]] == t_counter[s[i]] - 1:
                    matches -= 1
                i += 1
                
            # update answer
            if matches == chars:
                if not answer:
                    answer = s[i:j+1]
                elif (j - i + 1) < len(answer):
                    answer = s[i:j+1]
        
        return answer

t 와 s 의 Counter 를 각각 구해준다

substring = s[i:j+1] 라고 생각하면 될 듯

if matches < chars:

=> substring 을 찾아야 하는 상태 (j 만 움직임)
if j == len(s) - 1: 는 더이상 substring 이 없다는 것이므로 answer 를 리턴
t 에 값이 있고 (중복일 경우) 개수도 맞다면 matches += 1

else:

=> 새로운 substring 을 찾기 위해서 맨 앞을 한칸씩 오른쪽으로 옮김 (i 만 움직임)
맨 앞 문자가 t 에 있으면 matches -= 1 해서 다시 substring 찾게 함

if matches == chars:

=> minimum substring 으로 update