A-019● Day 192026.05.21hardleetcode #76neetcode150

Minimum Window Substring

#hash-table#string#sliding-window

↗ leetcode #76 · minimum-window-substring

Problem

· problem

P.019

Minimum Window Substring

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "". The testcases will be generated such that the answer is unique.

constraints

· 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

// paraphrased summary — see source for full text

examples

example 1input → output

"ADOBECODEBANC"
"ABC"

BANC

example 2input → output

"a"
"a"

example 3input → output

"a"
"aa"

Pre-solve

· pre-solve

● 1list shown→● 2select→● 3reveal

☐
What if s contains characters not in t?
☐
Can the result be an empty string?
☐
Must we match exact character frequencies?
☐
Should we check all possible substrings?
☐
Must we track all characters in s, even those not in t?
☐
What if t is longer than s?
☐
What does the 'have' variable represent?

check the items you would ask, then press confirm

// session-only state — refresh resets (repeatable practice)

Logic Structure

· logic

● 1slots shown→● 2pick per slot→● 3reveal

// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.

step 1· Early Termination Check

○

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· Build Target Frequency Map

○

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

○

countT = set(t)

○

countT[c] = 1

○

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

step 3· Initialize Tracking Variables

○

have, need = 0, len(countT)

○

have, need = 0, len(t)

○

have, need = len(countT), 0

○

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

step 4· Expand Window and Update Counts│ nested

○

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· Check if Character Requirement Met│ nested

○

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· Shrink Window While Valid│ nested

○

while have == need:

○

while have < need:

○

while have > 0:

○

if have == need:

step 7· Remove Left Character and Adjust Tracking│ │ nested

○

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

pick one option per slot

// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.

Solve · Trace

· 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 ""

mental dry-run cases

// walk each case in your head; expand the worked example below if stuck.

case 1

"ADOBECODEBANC"
"ABC"

→

BANC

case 2

"a"
"a"

→

case 3

"a"
"aa"

→

// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.