LeetCode · #76

Minimum Window Substring Solution

Given strings s and t, return the minimum window in s that contains all characters of t.

Section One · Problem

Problem Statement

🏷️

Difficulty

Hard

🔗

LeetCode

Problem #76

🏗️

Pattern

Sliding Window — expand then shrink

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 no such window exists, return the empty string "".

Example

 Input: s = "ADOBECODEBANC",  t = "ABC" Output: "BANC" // "BANC" contains A, B, C. No shorter window does. 

Example 2

 Input: s = "a",  t = "aa" Output: "" // Need two 'a's but s has only one → impossible 

Constraints

 • 1 ≤ s.length, t.length ≤ 10⁵ • s and t consist of uppercase and lowercase English letters 

Section Two · Approach 1

Brute Force — O(n² · m)

Check every substring of s to see if it contains all characters of t. For each substring, build a frequency map and compare. Track the shortest valid one.

Problem: O(n²) substrings, each costing O(m) to verify. A sliding window expands right to cover all characters, then shrinks left to minimize — hitting each character at most twice for O(n + m) total.

Java — Brute Force (TLE)

 class Solution {
public String minWindow(String s, String t) {
String result = "";
for (int i = 0; i < s.length(); i++) {
for (int j = i + t.length(); j <= s.length(); j++) {
String sub = s.substring(i, j);
if (containsAll(sub, t))
if (result.isEmpty() || sub.length() < result.length())
                        result = sub;
            }
        }
return result;
    }
// helper to check if sub contains all chars of t private boolean containsAll(String sub, String t) {
int[] count = new int[128];
for (char c : sub.toCharArray()) count[c]++;
for (char c : t.toCharArray()) if (--count[c] < 0) return false;
return true;
    }
}

Python — Brute Force (TLE)

 from collections import Counter class Solution:
def minWindow(self, s: str, t: str) -> str:
        t_count = Counter(t)
        result = "" for i in range(len(s)):
for j in range(i + len(t), len(s) + 1):
if not (t_count - Counter(s[i:j])):
if not result or j - i < len(result):
                        result = s[i:j]
return result

Metric	Value
Time	O(n² · m)
Space	O(m)

Section Three · Approach 2

Sliding Window — O(n + m)

Two phases that repeat: expand the right pointer until the window contains all characters of t, then shrink the left pointer to find the minimum valid window. Track when all required characters are satisfied using a formed counter.

💡 Mental model: Imagine you're casting a fishing net (the window) in a river of characters. First, you widen the net rightward until you've caught all the required fish (characters of t). Then you tighten the left side to use the smallest possible net — as soon as a required fish escapes, you stop tightening and expand right again. You record the smallest net size that ever held all targets.

Algorithm

Step 1: Build tCount — frequency map of t. Let required = number of unique characters in t.
Step 2: Maintain windowCount for the current window and formed = how many unique chars in t are fully satisfied.
Step 3: Expand right: add s[right] to windowCount. If windowCount[c] == tCount[c], increment formed.
Step 4: While formed == required: record window if smaller than best, then shrink left — decrement windowCount[s[left]], if it drops below tCount, decrement formed. left++.

🎯 Key insight — formed counter:

Instead of comparing entire frequency maps each step (O(52)), we track how many of t's unique characters are fully satisfied.
When a character's window count reaches its required count, formed++.
When it drops below, formed--. Checking formed == required is O(1).

Section Four · Trace

Visual Walkthrough

Trace through s = "ADOBECODEBANC", t = "ABC":

Expand right to cover, shrink left to minimize

Section Five · Implementation

Code — Java & Python

Java — Sliding Window

 import java.util.HashMap;
class Solution {
public String minWindow(String s, String t) {
if (t.length() > s.length()) return "";
HashMap<Character, Integer> tCount = new HashMap<>();
for (char c : t.toCharArray()) tCount.merge(c, 1, Integer::sum);
int required = tCount.size();
int formed = 0;
HashMap<Character, Integer> window = new HashMap<>();
int left = 0, minLen = Integer.MAX_VALUE, minStart = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
            window.merge(c, 1, Integer::sum);
if (tCount.containsKey(c) && window.get(c).intValue() == tCount.get(c).intValue())
                formed++;
while (formed == required) {
if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minStart = left;
                }
char leftChar = s.charAt(left);
                window.put(leftChar, window.get(leftChar) - 1);
if (tCount.containsKey(leftChar) &&
                    window.get(leftChar) < tCount.get(leftChar))
                    formed--;
                left++;
            }
        }
return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
    }
}

Python — Sliding Window

 from collections import Counter class Solution:
def minWindow(self, s: str, t: str) -> str:
if len(t) > len(s): return ""
t_count = Counter(t)
        required = len(t_count)
        formed = 0
window = {}
        left = 0
min_len = float('inf')
        min_start = 0 for right in range(len(s)):
            c = s[right]
            window[c] = window.get(c, 0) + 1 if c in t_count and window[c] == t_count[c]:
                formed += 1 while formed == required:
if right - left + 1 < min_len:
                    min_len = right - left + 1
min_start = left

                window[s[left]] -= 1 if s[left] in t_count and window[s[left]] < t_count[s[left]]:
                    formed -= 1
left += 1 return "" if min_len == float('inf') else s[min_start:min_start + min_len]

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute Force	O(n² · m)	O(m)	Check all substrings
Sliding Window ← optimal	O(n + m)	O(m)	Each char enters/leaves window once. O(m) for t's freq map.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
t longer than s	`s="a", t="aa"`	Impossible → return "".
Exact match	`s="abc", t="abc"`	The entire string is the minimum window.
Duplicate chars in t	`s="aa", t="aa"`	Need two a's. Window count must meet the required count for each char.
Single char	`s="abcda", t="a"`	Minimum window is "a" at index 0 (or 4). Length 1.
No valid window	`s="abc", t="d"`	Character d doesn't exist in s → "".
Case sensitive	`s="Aa", t="a"`	'A' ≠ 'a'. Only index 1 matches. Use int[128] for ASCII.

⚠ Common Mistake: Using == to compare Integer objects in Java. window.get(c) == tCount.get(c) compares references, not values, for integers outside the cached range [-128, 127]. Use .intValue() or .equals() to compare correctly.

← Back to Sliding Window problems

LearningTree

LC 76 · Minimum Window Substring — Solution & Explanation | DSA Guide