[리트코드] 76. Minimum Window Substring

76. Minimum Window Substring

Problem

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

t를 만족하는 s의 최소 부분 문자열 찾기

Constraints:

• m == s.length
• n == t.length
• 1 <= m, n <= 105
• s and t consist of uppercase and lowercase English letters.

풀이

start는 고정 시켜놓고 end를 움직이면서 해당 window가 유효한지 (t의 원소를 다 가지고 있는지)를 확인한다.

만약 유효하다면 정답을 업데이트하고 유효하지 않을 때까지 start를 움직인다.

T = ABC

S = ADOBECODEBANC를 예로 나타내면 아래와 같다.

ADOBEC

DOBECO

DOBECOD

DOBECODE

DOBECODEB

DOBECODEBA

OBECODEBAN

BECODEBAN

ECODEBAN

CODEBAN

ODEBAN

ODEBANC

DEBANC

EBANC

BANC

ANC

class Solution:
    
    def minWindow(self, s: str, t: str) -> str:
        
        target_cnt = collections.Counter(t)
        target_len  = len(t)
        start = 0
        answer = ""
        
        for end in range(len(s)):
            
            # t의 원소일 경우 
            if target_cnt[s[end]] > 0 :
                target_len -= 1
            
            target_cnt[s[end]] -= 1
            
            while target_len == 0:
                
                if not answer or len(s[start:end + 1]) < len(answer):
                    answer = s[start:end + 1]
                target_cnt[s[start]] += 1
                
                if target_cnt[s[start]] > 0:
                    target_len += 1
                    
                start += 1
        
        
        return answer