문제

• 문자열 s 길이 m
• 문자열 t 길이 n
• t에 있는 글자들을 포함하는 s의 min window substring 출력
• duplicate 고려

풀이

• 저번에 풀었던 window 알고리즘 이용해야 할 듯
• t의 원소의 갯수를 나타내는 dict 만들고
• window 안의 문자열 개수로 dict에서 수 빼기
• dict의 value 가 다 0인 것 중 가장 짧은 길이의 문자열이 정답

from collections import defaultdict
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        countDict = defaultdict(int)
        for letter in t:
            countDict[letter] += 1

        lenS = len(s)
        start = 0
        end = 0
        if s[start] in countDict:
            countDict[s[start]] -= 1

        minLen = 10 ** 5 + 1
        minStr = ""
        while start <= end < lenS:
            # t의 모든 글자를 포함하는 substring
            if all(value <= 0 for value in countDict.values()):
                thisLen = end - start + 1
                if thisLen < minLen:
                    # 길이가 최소면
                    minLen = thisLen
                    minStr = s[start:end + 1] # 저장
                    
                if s[start] in countDict:
                    countDict[s[start]] += 1 # 시작지점 한칸 뒤로 보내기
                start += 1
            else:
                # substring에 t의 모든 글자가 들어가지 않아
                # end만 +1 해서 길이 늘려줌
                end += 1
                if end < lenS and s[end] in countDict:
                    countDict[s[end]] -= 1
        return minStr

결과