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.lengthn == t.length1 <= m, n <= 105s and t consist of uppercase and lowercase English letters.
Follow up: Could you find an algorithm that runs in O(m + n) time?
Problem Overview: Given two strings s and t, find the smallest substring in s that contains every character from t (including duplicates). If no such substring exists, return an empty string. The challenge is minimizing the window while ensuring all required characters are present.
Approach 1: Generate All Substrings and Check Validity (O(n^3) time, O(1) space)
The brute force strategy enumerates every possible substring of s. For each substring, count character frequencies and compare them with the required counts from t. If the substring contains all required characters, update the minimum length window. This involves two nested loops to generate substrings and another pass to verify character counts, which leads to roughly O(n^3) time in the worst case. Space usage remains O(1) if the alphabet size is fixed. This approach helps you reason about the problem constraints but quickly becomes too slow for larger inputs.
Approach 2: Sliding Window with HashMap (O(n) time, O(k) space)
The optimal solution uses the sliding window technique with a frequency map built using a hash table. First, store the frequency of each character required from t. Use two pointers (left and right) to maintain a window over s. As the right pointer expands the window, update counts and track how many required characters have been satisfied. Once the window contains all characters from t, move the left pointer forward to shrink the window while maintaining validity. Each character enters and leaves the window at most once, so the algorithm runs in O(n) time with O(k) space, where k is the number of unique characters in t.
The key insight is maintaining a dynamic window that expands to satisfy constraints and contracts to remove unnecessary characters. A counter tracks how many characters currently meet the required frequency. This avoids repeatedly recomputing counts for every substring and turns a cubic brute force search into a linear pass through the string.
Because the solution relies on sequential scanning and character frequency tracking, understanding how pointers move and when counts are updated is critical. Problems involving minimum or maximum subarrays with constraints frequently use this same pattern across string and array problems.
Recommended for interviews: The sliding window with hashmap approach is the expected interview solution. Interviewers want to see whether you recognize the pattern of expanding and contracting a window while maintaining frequency counts. Mentioning the brute force method shows you understand the search space, but implementing the linear O(n) sliding window demonstrates strong problem‑solving and pattern recognition skills.
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.
C++
Java
Python
C#
JavaScript
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).
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.
C++
Java
Python
C#
JavaScript
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.
| Approach | Complexity |
|---|---|
| Sliding Window with Hashmap | Time Complexity: O(m + n) since each character in "s" and "t" is processed at most twice. |
| 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Generate All Substrings and Check Validity | O(n^3) | O(1) | Useful for understanding the problem or very small input sizes |
| Sliding Window with HashMap | O(n) | O(k) | Optimal solution for large strings and the standard interview approach |
Minimum Window Substring - Airbnb Interview Question - Leetcode 76 • NeetCode • 385,124 views views
Watch 9 more video solutions →Practice Minimum Window Substring with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor