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.
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.
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.
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.
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]:
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.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.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.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.
| 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. |
| Counting + Two Pointers | — |
| 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 |
Minimum Window Substring - Airbnb Interview Question - Leetcode 76 • NeetCode • 495,660 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