575페이지 부분문자열이 포함된 최소 윈도우 sol2 질문입니다.

[AsterGoldman]

전체 코드입니다. 실행과정 중 이해가 안가는 부분이 있어서 질문 올립니다.

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = collections.Counter(t)
        missing = len(t)
        left = start = end = 0

        for right, char in enumerate(s,1):
            missing -= need[char]>0
            need[char] -= 1
            ###
            if missing == 0: #여기부분이 이해가 안되는 부분입니다
                while left<right and need[s[left]]<0:
                    need[s[left]]+=1
                    left += 1    
            ###
                if not end or right - left <= end - start:
                    start , end = left, right
                    need[s[left]] += 1
                    missing += 1
                    left += 1
        return s[start:end]

---

이해가 안가는 코드 단을 #으로 표기했습니다. s = "ADOBECODEBANC" 이고 t="ABC 인 테스트 케이스에서 실행 중 이해가 안되는 부분이 있습니다. if missing == 0: 인부분이 처음으로 걸리는 때가 right = 6이고 그 때 가르키는 문자가 첫번 째 C 입니다. 즉, s 중에서 ADOBEC 까지 순회했을 때 missing==0조건에 처음 걸리게 되는데요. 이 때 need를 살펴보면 {A:0, B:0, C:0, D=-1, O=-1, E=-1}로 t에 해당하는 값들(찾아야 하는 값들)은 0인 반면에 다른 값들은 -1로 잘 설정 되어있는 것 까지 확인했습니다. 그런데 그 밑에 while 문 조건이 이해가 안갑니다. left 가 0으로 시작하기 때문에 need[s[left]] 즉 need[A]=0 이므로 while 조건문에 해당되지 않아 순회가 불가능 하다고 생각하는데 왜 정상적으로 루프가 도는지 이해가 되지 않습니다. ##안에 있는 left를 오른쪽으로 보낼 수 없기 때문에 슬라이딩 윈도우를 줄일 수 없을거라 생각했는데 제가 어디서 잘 못 생각한 걸까요?

[PARKINHYO]

if missing == 0:
    while left < right and need[s[left]] < 0:
        need[s[left]] += 1
        left += 1

    if not end or right - left <= end - start:
        start, end = left, right
        need[s[left]] += 1
        missing += 1
        left += 1

위의 while문은 t에 포함된 문자열이 아닌 문자열을 판단하기 위한 코드입니다. 즉 s='ADOBECODEBANC'에서 D, O, E, N 문자열 need 원소의 값이 음수이면 need 원소에서 해당 문자열을 1증가, left를 오른쪽으로 1칸 옮깁니다.

@AsterGoldman님이 말씀하신건 아래 if문에서 left가 이동할 것 같습니다. 처음에는 end가 0이니깐 not end 코드로 인해 if 문 안쪽으로 들어오고 현재 left, right를 start, end에 저장한뒤에 need[s[left]] += 1로 need[A]의 값이 0에서 1로 되고, missing도 1로 증가, left도 오른쪽으로 1칸 이동해서 더 짧은 구간이 있나 탐색을 계속하게 됩니다.

[AsterGoldman]

감사합니다 제가 위에 부분에 묶여서 전체적인 흐름을 살피는데 미흡했던 것 같습니다. 시야를 넓게하고 생각의 궤를 제대로 찾은 것 같습니다! 정말 감사합니다!