Minimum Window Substring is the last and toughest stop in our sliding window run, and it is Day 12 of the Tekraze DSA series. It is a famous hard level interview question, but if you followed the last two days, you already know every move it needs. Today we just put them together.
Also Read: Day 11, Longest Repeating Character Replacement shows the grow-and-shrink window this post builds on.
What is the Minimum Window Substring problem?
You get two strings, s and t. Return the smallest substring of s that contains every character of t, including duplicates. If no such window exists, return an empty string. You can also try it on LeetCode, where it is problem 76 and rated hard.
Minimum Window Substring examples
text
Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" Why: "BANC" holds A, B and C, and no shorter window does Input: s = "a", t = "aa" Output: "" Why: s has only one a, so t can never be covered
How should you think about it in plain words?
Here is Minimum Window Substring in plain words. Picture a stretchy window over s. Grow the right side until the window holds everything t asks for. Now it is valid, but maybe too wide, so pull the left side in as long as it stays valid, noting the size each time.
The moment it breaks, go back to growing on the right. You keep a small shopping list of what is still missing, and the window ticks items off as it grows.
What does the brute force solution look like?
Check every substring and test whether it covers t, keeping the shortest one that does. It is the easiest way to see the Minimum Window Substring problem before we make it fast.
python
from collections import Counter
def min_window_brute(s, t):
need, best = Counter(t), ""
for i in range(len(s)):
for j in range(i + 1, len(s) + 1):
if not need - Counter(s[i:j]):
if not best or j - i < len(best):
best = s[i:j]
break
return best
Time is O(n² × (n + m)) in the worst case, since there are about n² substrings and each Counter check costs time in proportion to the substring length. Space is O(m) for the counters. It works on tiny inputs and times out on anything real.
How do we get the optimal Minimum Window Substring solution?
Build a need count from t and a number missing equal to the length of t. Move right across s. If the new character was still needed, lower missing, then lower its count in need either way. Extra characters simply go negative.
When missing hits 0 the window covers t. Record it if it is the shortest so far, then give back the left character by raising its count. If that count becomes positive, the window just lost something it needed, so raise missing and go back to growing.
The Minimum Window Substring solution runs in O(m + n) time, where n is the length of s and m is the length of t, because each pointer crosses s only once. Space is O(1) with a fixed 128 slot array for ASCII, or O(k) for k distinct characters with a hash map.
Minimum Window Substring in Java
java
public class Solution {
public static String minWindow(String s, String t) {
if (s.isEmpty() || t.isEmpty()) return "";
int[] need = new int[128];
for (char c : t.toCharArray()) need[c]++;
int missing = t.length(), left = 0, start = 0, best = Integer.MAX_VALUE;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (need[c] > 0) missing--;
need[c]--;
// window covers t, so shrink it from the left
while (missing == 0) {
if (right - left + 1 < best) { best = right - left + 1; start = left; }
char l = s.charAt(left++);
need[l]++;
if (need[l] > 0) missing++;
}
}
return best == Integer.MAX_VALUE ? "" : s.substring(start, start + best);
}
public static void main(String[] args) {
String[][] tests = {{"ADOBECODEBANC", "ABC", "BANC"}, {"a", "a", "a"}, {"a", "aa", ""},
{"ab", "b", "b"}, {"aa", "aa", "aa"}, {"", "a", ""}, {"bba", "ab", "ba"}};
for (String[] x : tests) {
String got = minWindow(x[0], x[1]);
System.out.println((got.equals(x[2]) ? "PASS " : "FAIL ") + x[0] + " " + x[1] + " -> " + got);
}
}
}
Minimum Window Substring in Python
python
from collections import Counter
def min_window(s, t):
if not s or not t:
return ""
need = Counter(t)
missing = len(t) # characters of t still not covered
left = start = 0
best = float("inf")
for right, ch in enumerate(s):
if need[ch] > 0:
missing -= 1
need[ch] -= 1
# window covers t, so shrink it from the left
while missing == 0:
if right - left + 1 < best:
best, start = right - left + 1, left
need[s[left]] += 1
if need[s[left]] > 0:
missing += 1
left += 1
return "" if best == float("inf") else s[start:start + best]
tests = [("ADOBECODEBANC", "ABC", "BANC"), ("a", "a", "a"), ("a", "aa", ""),
("ab", "b", "b"), ("aa", "aa", "aa"), ("", "a", ""), ("bba", "ab", "ba")]
for s, t, want in tests:
got = min_window(s, t)
print("PASS" if got == want else "FAIL", repr(s), repr(t), "->", repr(got))
Minimum Window Substring in Rust
rust
fn min_window(s: &str, t: &str) -> String {
if s.is_empty() || t.is_empty() {
return String::new();
}
let b = s.as_bytes();
let mut need = [0i32; 128];
for c in t.bytes() {
need[c as usize] += 1;
}
let (mut missing, mut left, mut start, mut best) = (t.len(), 0usize, 0usize, usize::MAX);
for right in 0..b.len() {
let c = b[right] as usize;
if need[c] > 0 {
missing -= 1;
}
need[c] -= 1;
// window covers t, so shrink it from the left
while missing == 0 {
if right - left + 1 < best {
best = right - left + 1;
start = left;
}
let l = b[left] as usize;
need[l] += 1;
if need[l] > 0 {
missing += 1;
}
left += 1;
}
}
if best == usize::MAX { String::new() } else { s[start..start + best].to_string() }
}
fn main() {
let tests = [("ADOBECODEBANC", "ABC", "BANC"), ("a", "a", "a"), ("a", "aa", ""),
("ab", "b", "b"), ("aa", "aa", "aa"), ("", "a", ""), ("bba", "ab", "ba")];
for (s, t, want) in tests {
let got = min_window(s, t);
println!("{} {:?} {:?} -> {:?}", if got == want { "PASS" } else { "FAIL" }, s, t, got);
}
}
Do all three Minimum Window Substring solutions pass the tests?
All three programs ran on the same seven tests, including “ADOBECODEBANC” with “ABC”, a target longer than the string, duplicate letters in t, an empty string and “bba” with “ab”. Every test passed in Java, Python and Rust.
Also Read: Day 10, Longest Substring Without Repeating Characters uses the same window idea with a simpler rule for when to shrink.
What are the 6 tips and tricks for an easy solution?
- Spot the pattern. For Minimum Window Substring, the smallest continuous part of a string that contains all of something is the classic shrinking sliding window.
- Use one missing counter. Tracking a single number of missing characters is much easier than comparing two maps on every step.
- Let counts go negative. Negative values mean extras inside the window, which is exactly what lets you shrink safely.
- Store start and length, not the substring. Slicing only once at the end keeps the solution truly linear.
- Test the edges. Try t longer than s, duplicate letters in t, an answer that is the whole string, and no answer at all.
- Explain the two phases first. In an interview, say “expand until valid, shrink while valid” before you code. Then the code reads like your explanation.
What are the common mistakes people make?
These are the slips that break most first attempts at the Minimum Window Substring problem:
- Ignoring duplicates in t, so “AA” is treated the same as “A”.
- Comparing full maps on every step, which turns a linear solution into a slow one.
- Updating the best answer after shrinking instead of before, which records an invalid window.
- Building substrings inside the loop and paying for copies each time.
- Returning a leftover window when no valid window was ever found.
Where is this pattern used in the real world?
Minimum Window Substring is more than an interview trick. Search engines use it to find the shortest snippet of a page that contains all the words you typed, which is what you see under each result. Log tools find the tightest time span where a set of events all happened, which helps when tracing a bug.
Genome research looks for the smallest region that holds a set of markers. Shopping or travel apps can find the shortest stretch of a route that passes every stop on a list.
Which earlier posts in the series should you read?
If the Minimum Window Substring problem feels like a lot, go back and read the pieces it is built from:
- Day 1, Two Sum for hash map basics.
- Day 2, Best Time to Buy and Sell Stock for tracking the best answer in one pass.
- Day 3, Contains Duplicate, Day 4, Valid Anagram and Day 5, Group Anagrams for the counting toolkit we lean on for window frequencies.
- Day 6, Valid Palindrome, Day 7, Two Sum II, Day 8, 3Sum and Day 9, Container With Most Water for the two pointer moves that the sliding window grows out of.
- Day 10, Longest Substring Without Repeating Characters and Day 11, Longest Repeating Character Replacement for the start of the sliding window section.
Keep our data structures cheat sheet handy as a quick reminder of which structure fits which job.
Conclusion
Minimum Window Substring looks scary, but it is just two phases: grow until the window is valid, then shrink while it stays valid. One missing counter and a count array do all the work in O(m + n) time. Once you can solve Minimum Window Substring from memory in your favorite language, check it against the seven tests above. Next up we step into stacks.
Frequently asked questions
What is the time complexity of Minimum Window Substring?
The sliding window solution runs in O(m + n) time, where n is the length of s and m is the length of t. Space is O(1) with a fixed ASCII array, or O(k) with a hash map.
Why is Minimum Window Substring marked as hard?
It mixes counting with duplicates, a window that both grows and shrinks, and careful timing of when to record the answer. Each idea is simple, but all of them must work together.
How does the missing counter work?
It starts at the length of t and drops each time the window gains a character it still needs. When it reaches 0 the window covers t, and it rises again when shrinking removes a needed character.
What should you return when no window exists?
Return an empty string. Track the best length with a very large starting value and check it at the end before slicing.
How is Minimum Window Substring different from Longest Substring Without Repeating Characters?
That problem looks for the longest valid window, so it shrinks only when the window breaks. This one looks for the shortest valid window, so it shrinks while the window is still valid.
