Skip to main content
Talentd

Minimum Window Substring - Solution & Explanation

HardHash TableStringSliding Window30 min readAsked at: Amazon, Microsoft, Apple +32
Practice this problem

Problem Statement

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.

 

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

 

Constraints:

  • m == s.length
  • n == t.length
  • 1 <= m, n <= 105
  • s and t consist of uppercase and lowercase English letters.

 

Follow up: Could you find an algorithm that runs in O(m + n) time?

Approach Overview

Problem Overview: You are given two strings s and t. The goal is to find the smallest substring of s that contains every character from t (including duplicates). If no such substring exists, return an empty string.

Approach 1: Generate All Substrings and Check Validity (O(nĀ² * k) time, O(k) space)

This brute force strategy generates every possible substring of s using two nested loops. For each substring, build a frequency map and compare it with the character requirements of t. If the substring contains all required characters with correct counts, update the minimum length window. The main cost comes from repeatedly validating substrings, which requires scanning character counts. Time complexity is O(nĀ² * k), where k is the number of unique characters in t. Space complexity is O(k) for the frequency map. This approach demonstrates the basic idea but becomes impractical for large inputs because it checks too many substrings.

Approach 2: Sliding Window with Hashmap (O(n) time, O(k) space)

The optimal solution uses the sliding window technique with a frequency map from a hash table. First build a map storing how many times each character appears in t. Use two pointers (left and right) to represent a window over s. Expand the window by moving right and updating counts when characters from t appear. Once the window contains all required characters, try shrinking it by moving left while still maintaining validity. Each valid window update checks if its length is smaller than the best result. Every character enters and leaves the window at most once, which keeps the total work linear. The time complexity is O(n) and space complexity is O(k), where k is the number of distinct characters in t. This pattern is common in string problems that require the smallest or largest valid substring.

Recommended for interviews: Interviewers expect the sliding window solution. Starting with the brute force method shows you understand the problem constraints and correctness. The sliding window with a hashmap demonstrates strong algorithmic thinking, reducing the search space from all substrings to a dynamically adjusted window while maintaining character counts in constant time.

Approach 1: Sliding Window with Hashmap

This approach uses a sliding window (two-pointer technique) along with hash maps to keep track of characters. One hash map counts all characters in the string "t", while another counts the current characters inside the window from the string "s". We expand the right pointer to include characters until we have a valid window containing all characters from "t", and then contract the left pointer to minimize the window size.

The C solution implements a sliding window using two hash maps. "required" maps store the count of each character needed from "t", and "window" maps store the count within the current window in "s". The outer loop expands the window to include new characters, while the inner loop attempts to shrink it to find the minimum valid window. The strndup function extracts the minimum window substring if it exists.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m + n) since each character in "s" and "t" is processed at most twice.
Space Complexity: O(1) since the size of the hashmap is limited to 128 characters (ASCII set).

Try this approach in the editor ā†’

Approach 2: Generate All Substrings and Check Validity

This alternative approach generates all possible substrings of "s" and checks each to see if it contains all the characters of "t" (including counts). Although not optimal, it serves as a conceptual fundamental check against the sliding window optimal approach by explicitly comparing substrings.

The C solution generates all start indexes and, for each, creates an end substring incrementally until it matches string "t". The isValid function is called to ensure the substring meets criteria. For legitimate substrings, it updates the minimal length found and extracts it for return.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m^2 * n) because of the double loop over the length of "s" and the complete scan for each "t" character.
Space Complexity: O(1) as the storage is minimal beyond fixed character occurrences.

Try this approach in the editor ā†’

Approach 3: Counting + Two Pointers

We use a hash table or array need to count the occurrences of each character in string t, and another hash table or array window to count the occurrences of each character in the sliding window. Additionally, we define two pointers l and r to point to the left and right boundaries of the window, a variable cnt to represent how many characters from t are already included in the window, and variables k and mi to represent the starting position and length of the minimum window substring.

We traverse the string s from left to right. For the current character s[r]:

  • We add it to the window, i.e., window[s[r]] = window[s[r]] + 1. If need[s[r]] geq window[s[r]], it means s[r] is a "necessary character", and we increment cnt by one.
  • If cnt equals the length of t, it means the window already contains all characters from t, and we can try to update the starting position and length of the minimum window substring. If r - l + 1 < mi, it means the current window represents a shorter substring, so we update mi = r - l + 1 and k = l.
  • Then, we try to move the left boundary l. If need[s[l]] geq window[s[l]], it means s[l] is a "necessary character", and moving the left boundary will remove s[l] from the window. Therefore, we need to decrement cnt by one, update window[s[l]] = window[s[l]] - 1, and move l one position to the right.
  • If cnt is not equal to the length of t, it means the window does not yet contain all characters from t, so we do not need to move the left boundary. Instead, we move r one position to the right and continue traversing.

After the traversal, if no minimum window substring is found, return an empty string. Otherwise, return s[k:k+mi].

The time complexity is O(m + n), and the space complexity is O(|\Sigma|). Here, m and n are the lengths of strings s and t, respectively; and |\Sigma| is the size of the character set, which is 128 in this problem.

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Sliding Window with Hashmap

Time Complexity: O(m + n) since each character in "s" and "t" is processed at most twice.
Space Complexity: O(1) since the size of the hashmap is limited to 128 characters (ASCII set).

Generate All Substrings and Check Validity

Time Complexity: O(m^2 * n) because of the double loop over the length of "s" and the complete scan for each "t" character.
Space Complexity: O(1) as the storage is minimal beyond fixed character occurrences.

Counting + Two Pointersā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Generate All Substrings and Check ValidityO(nĀ² * k)O(k)Good for understanding the problem or very small strings
Sliding Window with HashmapO(n)O(k)Optimal solution for large inputs and expected in coding interviews

Video Solution

Minimum Window Substring - Airbnb Interview Question - Leetcode 76 ā€¢ NeetCode ā€¢ 525,934 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Minimum Window Substring easy or hard?
Minimum Window Substring is classified as a Hard problem because managing the sliding window conditions correctly is tricky. Many candidates struggle with maintaining frequency counts and shrinking the window without breaking validity.
Minimum Window Substring Python/Java solution
Python and Java solutions typically implement the sliding window approach using a dictionary or HashMap for character counts. Two pointers track the current substring while counters track how many required characters are satisfied, ensuring the smallest valid window is found efficiently.
How to solve Minimum Window Substring in O(n)?
Use a sliding window with two pointers and a hashmap that stores required character counts from t. Move the right pointer to expand the window and include characters. When all required characters are present, move the left pointer to shrink the window and keep the substring minimal while updating the best answer.
What is the best approach for Minimum Window Substring?
The sliding window with a hashmap is the best approach. It tracks character frequencies from string t and expands or shrinks a window over string s to maintain a valid substring. Each character is processed at most twice, giving O(n) time complexity and O(k) space complexity where k is the number of unique characters in t.
Is Minimum Window Substring asked at Google/Amazon/Meta?
Minimum Window Substring frequently appears in interviews at companies like Google, Amazon, Meta, and Microsoft. It tests sliding window mastery, hashmap usage, and the ability to manage dynamic constraints in string problems.
What data structure is used in Minimum Window Substring?
The core data structure is a hashmap (or frequency array) that stores how many times each character from t must appear in the current window. Combined with two pointers, this structure enables constant-time updates while expanding or shrinking the substring window.
What is the time complexity of Minimum Window Substring?
The optimal sliding window solution runs in O(n) time where n is the length of string s. Each character is visited at most twice by the left and right pointers. The space complexity is O(k) for storing frequency counts of characters in t.

Ready to solve this problem?

Practice Minimum Window Substring with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Substrings That Can Be Rearranged to Contain a String I

Next

Count Substrings That Can Be Rearranged to Contain a String II