76. Minimum Window Substring

76. Minimum Window Substring

import collections

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        t_dict = collections.defaultdict(int)
        min_need_alpha = len(t)
        for alpha in t:
            t_dict[alpha] += 1
        
        ## 1)
        left = -1
        right = -1
        for i in range(len(s)):
            if left == -1 and s[i] in t_dict:
                left = i
                t_dict[s[i]] -= 1
                min_need_alpha -= 1
            elif s[i] in t_dict:
                t_dict[s[i]] -= 1
                if t_dict[s[i]] >= 0:
                    min_need_alpha -= 1
                if not min_need_alpha: 
                    right = i
                    break
    
        if min_need_alpha > 0: return ''
        if right == -1: return t
       	###
        
        ### 2)
        while True:
            if s[left] in t_dict:
                if t_dict[s[left]] == 0:
                    break
                t_dict[s[left]] += 1
            left += 1
        ###
        
        min_length = right - left + 1
        ans = s[left:right+1]
        
        ### 3)
        while True:
            right += 1
            while right < len(s) and s[left] != s[right]:
                if s[right] in t_dict:
                    t_dict[s[right]] -= 1
                right += 1
                
            if right == len(s):
                break
            
            t_dict[s[left]] -= 1
            
            while True:
                if s[left] in t_dict:
                    if t_dict[s[left]] == 0:
                        break
                    t_dict[s[left]] += 1
                left += 1
            if right - left + 1 < min_length:
                ans = s[left: right+1]
                min_length = right-left + 1
       	###
        
        return ans

문제 풀이

개략적으로 얘기하면 배열에서 가장 처음 만족하는 배열의 시작 index와 끝index를 찾습니다.

그리고 while을 통해 또 다른 배열의 조합이 있을때까지 찾습니다.

찾는 방법은

1. left위치의 문자와 right위치의 문자가 같을때 까지 right를 늘립니다.
2. 그리고 원하는 조건에 충족하는 한 최대한 left의 크기를 키웁니다.
3. 그리고 기존 substring을 비교하여 정답을 정합니다.

1번 과정을 통해서

• 원하는 조건이 충족되는지 체크
• s가 한 글자이고 t도 똑같이 한 글자인지 확인

2번 과정을 통해

• left를 더 오른쪽으로 당길 수 있는지 확인

3번 과정을 통해

• 오른쪽을 키우고 키운 만큼 왼쪽도 키워서 만족하는 가장 작은 substring찾기

## 리팩토링 해보자
import collections

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        t_dict = collections.defaultdict(int)
        min_need_alpha = len(t)
        for alpha in t:
            t_dict[alpha] += 1
        
        L, R = 0, -1
        left = 0
        for right in range(len(s)):
            if s[right] in t_dict:
                min_need_alpha -= t_dict[s[right]] > 0
                t_dict[s[right]] -= 1
            
            if min_need_alpha == 0:
                while s[left] not in t_dict or t_dict[s[left]] < 0:
                    if s[left] in t_dict:
                        t_dict[s[left]] += 1
                    left += 1
                if R == -1 or right - left < R - L:
                    R = right
                    L = left
        
        if min_need_alpha > 0: return ''
        return s[L:R+1]

과정을 여러번 반복하기 않고

1. right를 꾸준히 상승 시키고
2. right가 상승함에 따라 만족하는 substring이 되면
3. left를 최대한 상승시키고
4. 가장 짧은 구간의 left, right를 L,R에 저장
5. min_need_alpha가 0보다 크면 불가능하므로 빈 배열 리턴
6. 정답으로 가장 짧은 substring 리턴