LeetCode #76 Minimum Window Substring

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #76 Minimum Window Substring

문제 풀이

슬라이딩 윈도우를 쓰긴 하는데 그 범위가 가변적이란 점에서 투 포인터 쪽으로 생각함이 맞지 싶다. T에 들어있는 알파벳이 최소한 전부 포함되어 있음을 보장해야 한다는 점에서 필요한 글자와 들어간 글자의 현황을 명확히 해야 한다.

• T를 기준으로 Counter 객체를 생성한다.
• T의 길이만큼은 최소한 포함해야 하므로 missing 변수에 len(T)를 저장한다.
• 결과값을 갱신하여 저장할 start, end 포인터를 0으로 설정하고 좌측 포인터 left도 0으로 설장한다. 이후 조건 충족 시마다 최소 범위 탐색을 위해 left를 우측으로 이동시킬 예정이다.
• 모든 글자에 대해 탐색을 진행하고 그 좌표를 right이라 하자. 다만 파이썬은 A[left:right]의 경우 A[right - 1] 원소까지 조회하므로 right는 1부터 시작한다.
• 각 글자에 대해 만약 Counter의 값이 1이상이면 해당 글자가 T에 포함된 글자이며 윈도우 내에 모자란 상태임을 의미한다. 따라서 이 글자를 포함시킴에 따라 missing 값에서 1을 빼고 counter[S[right]]의 값도 1을 빼준다.
• 만약 missing이 0이 되어 T의 모든 알파벳이 윈도우 안에 들어왔다면 문제의 조건에 따라 최소 범위를 찾기 위해 left를 우측으로 옮겨야 한다. left < right 범위 내에서 현재 left 좌표의 글자를 빼려면 counter[S[left]]의 값이 음수여야 한다.(0인 상태면 left 좌표를 윈도우에서 뺄 경우 T의 알파벳 포함 조건에 위배됨) counter[글자]의 값이 음수라면 잉여 글자이므로 탐색 좌표의 counter값이 0이 될 때까지 반복한다.
• left 포인터를 우측으로 옮기는 과정이 끝나면 start와 end를 갱신해야 하는지 체크한다. 만약 end가 0으로 아직 한번도 갱신이 되지 않았거나 right - left <= end - start로 저장된 정답이 탐색 범위보다 크다면 갱신한다.
• 모든 순회가 끝나면 S[start:end]를 리턴한다.

python 코드

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        missing = len(t)
        counter = collections.Counter(t)
        left = start = end = 0
        for right in range(1, len(t) + 1):
            missing -= counter(s[right - 1]) > 0
            counter[s[right]] -= 1
            if missing == 0:
                while left < right and counter[s[left]] < 0:
                    counter[s[left]] += 1
                    left += 1
                if not end or right - left <= end - start:
                    start, end = left, right
                    missing += 1
                    counter[s[left]] += 1
                    left += 1
        return s[start:end]