Minimum Window Substring

Hard

📘 Problem Statement

Given two strings s and t of lengths m and n, 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 “”.

---

🔍 Example

s = "ADOBECODEBANC", t = "ABC"

Result : "BANC"

---

Intuition

use a frequency count of t and slide a window over s , checking for substring matches?”

• Use two pointers (left and right) to maintain a window.

• Use a need map to store frequencies of t.

• Use a window map to track what’s currently inside the window.

• Track how many characters meet their frequency requirements with a have counter.

• Once you find that your current window has all the characters of the target string, update your minimum str.

• Now reduce you window from left and take out characters until your window does loose any character in the target string, which is the time when you start expanding again from left.

🛠️ Solution

🧑‍💻 Code

def minWindow(s: str, t: str) -> str:
    if not s or not t:
        return ""
    
    need = Counter(t)
    window = {}
    have = 0
    need_count = len(need)
    res = [-1, -1]
    res_len = float('inf')

    left = 0
    for right in range(len(s)):
        char = s[right]
        if char in need:
            window[char] = window.get(char, 0) + 1
            if window[char] == need[char]:
                have += 1

        while have == need_count:
            # Update result
            if (right - left + 1) < res_len:
                res = [left, right]
                res_len = right - left + 1

            # Shrink window
            if s[left] in need:
                window[s[left]] -= 1
                if window[s[left]] < need[s[left]]:
                    have -= 1
            left += 1

    l, r = res
    return s[l:r+1] if res_len != float('inf') else ""

🕒 Time Complexity: \(O(m + n)\). 📦 Space Complexity: \(O(n)\) — for storing character maps