A-019● Day 192026.05.21hardleetcode #76neetcode150

최소 윈도우 부분문자열

#hash-table#string#sliding-window

↗ leetcode #76 · minimum-window-substring

문제

· problem

P.019

최소 윈도우 부분문자열

길이가 각각 m과 n인 두 문자열 s와 t가 주어졌을 때, t의 모든 문자(중복 포함)를 포함하는 s의 최소 윈도우 부분문자열을 반환하세요. 그러한 부분문자열이 없으면 빈 문자열 ""을 반환하세요. 테스트 케이스는 답이 유일하도록 생성됩니다.

제약

· 1 ≤ m, n ≤ 10^5 (lengths of s and t)
· s and t consist of uppercase and lowercase English letters
· Answer is guaranteed to be unique

// 지문은 본인 언어 요약 — 원문은 위 링크에서

입출력 예시

example 1input → output

"ADOBECODEBANC"
"ABC"

BANC

example 2input → output

"a"
"a"

example 3input → output

"a"
"aa"

사전 사고

· pre-solve

● 1리스트 출력→● 2선택→● 3정답 공개

☐
t에 없는 문자가 s에 포함되어 있으면 어떻게 되나요?
☐
결과가 빈 문자열일 수 있나요?
☐
문자의 정확한 빈도를 일치시켜야 하나요?
☐
가능한 모든 부분문자열을 확인해야 하나요?
☐
t에 속하지 않은 s의 모든 문자를 추적해야 하나요?
☐
t가 s보다 길면 어떻게 되나요?
☐
'have' 변수는 무엇을 나타내나요?

던질 질문에 체크하고 확인을 누르세요

// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)

논리 구조

· logic

● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개

// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.

step 1· 기본 경우 확인

○

if len(s) < len(t):

○

if len(s) == len(t): return ""

○

if len(t) == 0: return s

○

if len(s) > len(t) * 2: continue

step 2· 목표 문자 빈도 맵 구성

○

countT[c] = 1 + countT.get(c, 0)

○

countT = set(t)

○

countT[c] = 1

○

countT = {c: 1 for c in set(t)}

step 3· 추적 변수 초기화

○

have, need = 0, len(countT)

○

have, need = 0, len(t)

○

have, need = len(countT), 0

○

have, need = len(s), len(t)

step 4· 오른쪽 포인터로 윈도우 확장 및 카운트 업데이트│ 중첩

○

window[c] = 1 + window.get(c, 0)

○

window[c] = countT[c]

○

if c in countT: window[c] = 1 + window.get(c, 0)

○

window[s[r-1]] += 1

step 5· 문자 요구사항 충족 확인│ 중첩

○

if c in countT and window[c] == countT[c]:

○

if window[c] == countT[c]: have += 1

○

if c in countT and window[c] >= countT[c]: have += 1

○

if c in countT: have += 1

step 6· 모든 요구사항이 충족되면 윈도우 축소│ 중첩

○

while have == need:

○

while have < need:

○

while have > 0:

○

if have == need:

step 7· 왼쪽 문자 제거 및 추적 조정│ │ 중첩

○

window[s[l]] -= 1

○

window[s[l]] -= 1; l += 1

○

l += 1; window[s[l]] -= 1

○

if window[s[l]] < countT[s[l]]: have -= 1

각 슬롯에 한 줄씩 골라보세요

// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.

문제풀이 · 트레이스

· solve

solution.py

class Solution:

    def minWindow(self, s: str, t: str) -> str:

        if len(s) < len(t):

            return ""

        countT, window = {}, {}

        for c in t:

            countT[c] = 1 + countT.get(c, 0)

        have, need = 0, len(countT)

        res, resLen = [-1, -1], float("infinity")

        l = 0

        for r in range(len(s)):

            c = s[r]

            window[c] = 1 + window.get(c, 0)

            if c in countT and window[c] == countT[c]:

                have += 1

            while have == need:

                # update our result

                if (r - l + 1) < resLen:

                    res = [l, r]

                    resLen = r - l + 1

                # pop from the left of our window

                window[s[l]] -= 1

                if s[l] in countT and window[s[l]] < countT[s[l]]:

                    have -= 1

                l += 1

        l, r = res

        return s[l : r + 1] if resLen != float("infinity") else ""

머릿속 dry-run 케이스

// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.

case 1

"ADOBECODEBANC"
"ABC"

→

BANC

case 2

"a"
"a"

→

case 3

"a"
"aa"

→

// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.