Watch 10 video solutions for Minimum Window Substring, a hard level problem involving Hash Table, String, Sliding Window. This walkthrough by NeetCode has 385,124 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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: 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 | Time | Space | When to Use |
|---|---|---|---|
| Generate All Substrings and Check Validity | O(n² * k) | O(k) | Good for understanding the problem or very small strings |
| Sliding Window with Hashmap | O(n) | O(k) | Optimal solution for large inputs and expected in coding interviews |