Leetcode 76. Minimum Window Substring

문제

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.

문자열 s와 t가 주어집니다.
문자열 t에 있는 모든 문자를 포함하는 가장 작은 s의 부분문자열을 구해 리턴하세요
답은 반드시 한개 이하가 존재하며, 답이 없을시 빈 문자열을 리턴하세요
대소문자를 구분합니다.

예시

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: BANC는 ABC를 전부 포함하면서 가장 작은 부분문자열이다.

제한

• $m == s.length$
• $n == t.length$
• $1 <= m, n<= 10^5$
• s와 t는 알파벳 소문자와 대문자로 구성되어있다.

풀이

1. 먼저 t에 나오는 모든 문자의 갯수를 카운팅해 dict 자료형에 집어 넣는다.

        characters = dict()
        for ch in t:
            if ch in characters:
                characters[ch] += 1
            else:
                characters[ch] = 1
                
        # t 가 'ABC' 일시, {'A': 1, 'B': 1, 'C': 1} 이 된다.

2. Sliding window 를 만드는데, 이때 t를 구성하는 문자가 나오는 경우만 카운팅한다.

        for right, ch in enumerate(s):
            if ch in characters:
                characters[ch] -= 1
                if characters[ch] >= 0:
                    count += 1

3. 유효 카운팅이 t의 길이와 같다는것은 이 부분 문자열이 t의 모든 문자를 포함한다는 의미이기에 왼쪽부터 길이를 줄여나간다.

                if count == length:
                    have = True
                    while left <= right:
                        if s[left] in characters:
                            characters[s[left]] += 1
                            if characters[s[left]] > 0:
                                count -= 1
                                ans = ans if len(ans) < (right-left+1) else s[left:right+1]
                                left += 1
                                break
                        left += 1

• 이때 만약 t에 존재하는 문자를 왼쪽에서 제거한다면 이걸 제거했을때 ( 다시 dict에서 1을 늘릴때 ) 갯수가 1이 된다면 더이상 모든 문자를 포함하지 않는다는 것이기에 그 지점에서 검사를 하고, 아니면 계속 지워나간다.

4. 전체 절차를 마치고 한번도 모든 문자가 포함되지 않았을 경우는 빈 문자열을 아니면 결과를 리턴한다.

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        
        if len(s) < len(t): return ""
        
        characters = dict()
        for ch in t:
            if ch in characters:
                characters[ch] += 1
            else:
                characters[ch] = 1
                
        length = len(t)
        count = 0
        
        left = 0
        
        ans = s
        
        have = False
        
        for right, ch in enumerate(s):
            if ch in characters:
                characters[ch] -= 1
                if characters[ch] >= 0:
                    count += 1
                
                if count == length:
                    have = True
                    while left <= right:
                        if s[left] in characters:
                            characters[s[left]] += 1
                            if characters[s[left]] > 0:
                                count -= 1
                                ans = ans if len(ans) < (right-left+1) else s[left:right+1]
                                left += 1
                                break
                        left += 1
                        
        if not have: return ""

        return ans

여담

• 왠지 모르겠는데 sliding window 문제가 자주 나오는 경향이 있다...