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?
The key idea for Minimum Window Substring is to efficiently track a substring of s that contains all characters of t. A brute-force approach that checks every possible substring would be too slow, leading to quadratic or worse complexity.
A more optimal strategy uses the Sliding Window technique combined with a Hash Table. First, store the frequency of each character required from t. Then expand a window with two pointers over s, updating counts as characters enter the window. Once the window satisfies all required characters, attempt to shrink the left boundary to find the smallest valid window while still maintaining the requirement.
The algorithm repeatedly expands and contracts the window while tracking how many characters are satisfied. By ensuring each character is processed only a limited number of times, the solution runs efficiently with near-linear performance.
Time Complexity: O(n) where n is the length of the string. Space Complexity: O(k) for the frequency map of characters.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sliding Window with Hash Map | O(n) | O(k) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Use two pointers to create a window of letters in s, which would have all the characters from t.
Expand the right pointer until all the characters of t are covered.
Once all the characters are covered, move the left pointer and ensure that all the characters are still covered to minimize the subarray size.
Continue expanding the right and left pointers until you reach the end of s.
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.
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).
1from collections import Counter
2
3def minWindow(s: str, t: str) -> str:
4 required = Counter(t)
5
The Python solution uses Counter from the collections module to efficiently count character occurrences. The sliding window technique incrementally finds a valid window and attempts to minimize it whenever a complete valid form is found.
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.
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.
using System.Collections.Generic;
public class Solution {
public string MinWindow(string s, string t) {
if (s.Length < t.Length) return "";
Dictionary<char, int> required = new Dictionary<char, int>();
foreach (char c in t) {
if (!required.ContainsKey(c)) required[c] = 0;
required[c]++;
}
string result = "";
int min_len = int.MaxValue;
for (int start = 0; start < s.Length; ++start) {
Dictionary<char, int> window = new Dictionary<char, int>();
for (int end = start; end < s.Length; ++end) {
char c = s[end];
if (!window.ContainsKey(c)) window[c] = 0;
window[c]++;
if (end - start + 1 >= t.Length && IsValid(required, window)) {
if (end - start + 1 < min_len) {
min_len = end - start + 1;
result = s.Substring(start, end - start + 1);
}
break;
}
}
}
return result;
}
private bool IsValid(Dictionary<char, int> required, Dictionary<char, int> window) {
foreach (var kvp in required) {
if (window.GetValueOrDefault(kvp.Key) < kvp.Value) return false;
}
return true;
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Minimum Window Substring is a well-known hard problem frequently discussed in technical interview preparation. It tests understanding of sliding window techniques, hash maps, and optimization of substring problems.
Sliding window helps process the string in linear time by dynamically adjusting the substring boundaries. Instead of checking all substrings, it efficiently expands and contracts the window while maintaining character counts.
A hash map or frequency array is commonly used to store the required count of characters from the target string. It allows constant-time updates when expanding or shrinking the sliding window.
The optimal approach uses the sliding window technique with a hash map to track required character frequencies. Two pointers expand and shrink the window to maintain a valid substring containing all characters from the target string.
The C# code illustrates a comprehensible strategy utilizing Dictionaries that represent character needs and real-time window dynamics. It checks each substring for completeness via "IsValid", maintaining shortest valid subsequences alongside extensive checks across "s".