리트코드 76번 Minimum Window Substring (Python)

Problem

https://leetcode.com/problems/minimum-window-substring/description/

Solution

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        target = dict(Counter(t))
        need_count = len(t)
        left = 0
        start = end = -1

        for right, char in enumerate(s, start=1):
            # right
            if char in target.keys():
                if target[char] > 0:
                    need_count -= 1
                target[char] -= 1

            # left
            while left < right and target.get(s[left], -1) < 0:
                if s[left] in target.keys():
                    target[s[left]] += 1
                left += 1
                
            # set new start, end
            if need_count <= 0 and (start == end == -1 or right-left < end-start):
                start, end = left, right
        return s[start: end]

투 포인터와 슬라이딩 윈도우를 이용한 풀이이다. left, right 포인터 사이의 문자의 개수를 카운팅하면서 탐색하였다.

Reference

파이썬 알고리즘 인터뷰 76번