30% off Lifetime Premium Access expires December 2nd!

30% off Lifetime Premium Access expires Dec 2nd!

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Get Premium

Leetcode 76. Minimum Window Substring

Find the smallest substring of s that contains all characters of t (including duplicates), or return "" if none exists. This is typically solved with a sliding-window + frequency-count approach to track coverage and achieve O(m+n) time.

Asked at:

DESCRIPTION

Input:


s = "ADOBECODEBANC", t = "ABC"

Output:


"BANC"

Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t. No shorter substring contains all characters.

Constraints:

1 <= s.length, t.length <= 10^5
s and t consist of uppercase and lowercase English letters
The answer is guaranteed to be unique if it exists

Understanding the Problem

Let's understand what we're being asked to do. We have two strings: s = "ADOBECODEBANC" (the main string) and t = "ABC" (the target characters we need to find).

We need to find the smallest substring of s that contains all characters from t. In this example, "BANC" is the answer because it contains 'A', 'B', and 'C', and no shorter substring does.

Important constraint: If t has duplicate characters like "AABC", our substring must contain at least that many duplicates. So "ABC" wouldn't work - we'd need at least two 'A's.

Edge cases to consider: What if no valid substring exists? (return ""). What if t is longer than s? What if s itself is the minimum window? What if multiple windows have the same minimum length?

Brute Force Approach

The brute force approach generates all possible substrings of s and checks each one to see if it contains all characters from t (with correct frequencies). For each starting position, we expand to every possible ending position, checking character counts at each step. This requires nested loops and repeated character counting, making it highly inefficient for large inputs.

def min_window_substring(s, t):
    """
    Brute force approach: Generate all substrings and check each one.
    For each starting position, expand to every ending position.
    Check if substring contains all characters from t with correct frequencies.
    """
    if not s or not t:
        return ""
    
    # Count frequency of characters in t
    t_freq = {}
    for char in t:
        t_freq[char] = t_freq.get(char, 0) + 1
    
    min_length = float('inf')
    result = ""
    
    # Try every starting position
    for start in range(len(s)):
        # Try every ending position from start
        for end in range(start, len(s)):
            # Extract substring
            substring = s[start:end + 1]
            
            # Count frequency of characters in substring
            sub_freq = {}
            for char in substring:
                sub_freq[char] = sub_freq.get(char, 0) + 1
            
            # Check if substring contains all characters from t
            is_valid = True
            for char in t_freq:
                if sub_freq.get(char, 0) < t_freq[char]:
                    is_valid = False
                    break
            
            # Update result if valid and shorter
            if is_valid and len(substring) < min_length:
                min_length = len(substring)
                result = substring
    
    return result

Start brute force minimum window substring

0 / 1649

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n² * m) We generate O(n²) substrings, and for each substring we need O(m) time to verify it contains all characters from t, where n is length of s and m is length of t

Space Complexity: O(m + n) We need O(m) space to store character frequencies from t, and O(n) space for substring operations

Building Intuition

We need to track two things simultaneously: whether our current window contains all required characters, and whether we can shrink it while still maintaining coverage.

As we expand our window to the right, we're looking for coverage. Once we have all characters, we try to shrink from the left to find the minimum size.

Instead of checking every possible substring (which would be O(n²) or worse), we can use a two-pointer approach where the window expands and contracts dynamically.

This transforms an exponential problem into a linear one - we only pass through the string once with each pointer!

Imagine you're looking through a telescope with adjustable zoom. You start zoomed out (wide window) until you can see all the targets you need. Then you zoom in (shrink window) as much as possible while keeping all targets visible.

The key insight: once you've found a valid window, you don't need to restart from scratch - just slide the left edge forward until the window becomes invalid, then continue expanding the right edge. This sliding motion is what makes it efficient.

Common Mistakes

Not handling duplicate characters correctly - if t has two 'A's, the window must contain at least two 'A's, not just one

Forgetting to track the minimum window separately - you need to save the best result found so far, not just the current window

Inefficient validity checking - recounting all characters on each iteration instead of maintaining a running count of 'satisfied' characters

Off-by-one errors when extracting the final substring - make sure to use the correct start index and length from your tracked minimum

Not handling the case where no valid window exists - must return empty string, not null or the entire string

Optimal Solution

The optimal approach uses a sliding window with two pointers and frequency maps. First, build a frequency map of characters in t. Then expand the right pointer to grow the window until all required characters are covered. Once covered, shrink from the left to find the minimum valid window, tracking the smallest one found. Continue this expand-shrink cycle through the entire string, maintaining character counts to know when the window is valid.

def min_window_substring(s, t):
    """
    Find the smallest substring of s that contains all characters of t.
    Uses sliding window with frequency maps.
    """
    # Edge case: if t is longer than s, no solution exists
    if len(t) > len(s):
        return ""
    
    # Build frequency map for target string t
    t_freq = {}
    for char in t:
        t_freq[char] = t_freq.get(char, 0) + 1
    
    # Initialize window state
    required = len(t_freq)  # Number of unique characters in t
    formed = 0  # Number of unique characters in current window with desired frequency
    window_counts = {}
    
    # Initialize result tracking
    min_len = float('inf')
    min_left = 0
    min_right = 0
    
    # Two pointers for sliding window
    left = 0
    right = 0
    
    # Expand window with right pointer
    while right < len(s):
        # Add character from right to window
        char = s[right]
        window_counts[char] = window_counts.get(char, 0) + 1
        
        # Check if frequency of current character matches requirement
        if char in t_freq and window_counts[char] == t_freq[char]:
            formed += 1
        
        # Try to contract window from left while valid
        while left <= right and formed == required:
            # Update minimum window if current is smaller
            if right - left + 1 < min_len:
                min_len = right - left + 1
                min_left = left
                min_right = right
            
            # Remove character from left of window
            char = s[left]
            window_counts[char] -= 1
            
            # Check if window no longer satisfies requirement
            if char in t_freq and window_counts[char] < t_freq[char]:
                formed -= 1
            
            # Move left pointer forward
            left += 1
        
        # Move right pointer forward
        right += 1
    
    # Return result
    return "" if min_len == float('inf') else s[min_left:min_right + 1]

start

Start minimum window substring algorithm

0 / 85

Test Your Knowledge

Complexity Analysis

Time Complexity: O(m + n) We traverse string s once with the right pointer (O(n)) and at most once with the left pointer (O(n)), plus O(m) to build the frequency map of t. Each character is processed at most twice.

Space Complexity: O(m + k) We need O(m) space for the frequency map of t, and O(k) space for the window's character counts, where k is the number of unique characters (at most 52 for English letters)

What We've Learned

Sliding window with two pointers: Use the expanding-contracting window pattern when you need to find a substring that satisfies certain conditions - expand the right pointer to meet the condition, then contract the left pointer to optimize it. This transforms a brute-force O(n²) approach into O(n).
Frequency map comparison technique: Maintain two hash maps - one for the target character frequencies and one for the current window. Track a 'formed' counter that increments when a character reaches its required frequency, avoiding expensive full map comparisons on every iteration.
Window validity optimization: Instead of checking all character counts repeatedly, use a single integer 'formed' variable that equals the number of unique characters in t that have been satisfied in the current window. The window is valid when formed == required_unique_chars.
Premature window contraction pitfall: A common mistake is contracting the window (moving left pointer) before the window is valid. Always ensure your window first contains all required characters before attempting to minimize it, otherwise you'll miss valid solutions.
Character frequency tracking pattern: When problems ask for 'contains all characters including duplicates', immediately think frequency maps + sliding window. This pattern extends to problems like finding anagrams, permutations in string, or any 'contains all elements' substring problem.
Early termination optimization: Before starting the sliding window, check if len(s) < len(t) to return early. Also, filter s to only include characters present in t when s is much larger than t, reducing the search space significantly in sparse character scenarios.

Test Your Understanding

Why is sliding-window the right data structure for this problem?

sliding-window provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Late August, 2025

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 76. Minimum Window Substring

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact