💬 Discord
Sign In
NeetCode #254LC-76HardSliding WindowBlind 75NC 150NC 250
← Back to All Problems

#254 · #76 · Minimum Window Substring(最小覆盖子串)

📌 Problem Statement & Constraints

Given two strings s and t, return the minimum window substring of s that contains every character of t (with multiplicity). If no such window exists, return the empty string. Constraints: 1 <= s.length, t.length <= 10^5, uppercase and lowercase letters.

💡 Core Algorithmic Approaches

  1. Expand the right end while the window is missing characters; once the window is complete, shrink the left end to find the smallest valid window.
  2. Track missing, the number of characters still needed. Decrement it when the entering character is still required; increment it when a character that was required leaves the window.
  3. The window is complete exactly when missing == 0, at which point a candidate answer is recorded and the left pointer advances.
  4. The counts map is decremented below zero for surplus characters, which is what makes the missing accounting work.

💻 Benchmark Python3 Implementation

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        from collections import Counter
        need = Counter(t)
        missing = len(t)               # characters still required
        res = ""
        l = 0
        for r, ch in enumerate(s):
            if need[ch] > 0:
                missing -= 1           # this character was still needed
            need[ch] -= 1              # may go negative for surplus
            while missing == 0:        # window is complete -> try to shrink
                if not res or r - l + 1 < len(res):
                    res = s[l:r + 1]
                need[s[l]] += 1
                if need[s[l]] > 0:
                    missing += 1       # a required character left the window
                l += 1
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n + m): the right pointer advances n times and the left pointer at most n times, so the inner while is amortised O(n).
💾 Space Complexity
O(k) for the counters, where k is the alphabet size (at most 52 here).

⚠️ Interview Pitfalls & Follow-ups

  • Decrementing missing for surplus characters: only decrement when need[ch] > 0, i.e. when the character was genuinely still required.
  • Testing missing == 0 before decrementing need[ch]: the order matters -- check the need, then decrement.
  • Comparing window lengths incorrectly: the candidate length is r - l + 1.
  • Forgetting the missing += 1 when a required character leaves: without it, the loop would never terminate correctly.
  • Returning the whole string when t is empty: the constraints guarantee t is non-empty, but an empty t should return an empty string.