These are the notes for DSA episode 10, a classic hard string problem. Minimum Window Substring (LeetCode 76) asks for the shortest piece of a string s that contains every character of another string t, duplicates included. A brute force that restarts at every index is O(n²) and hits the time limit; a sliding window that grows on the right and shrinks on the left solves it in O(n + m) time and O(1) extra space. It is episode 9's window used the other way round: there we shrank a window to fix it, here we shrink a good window to make it smaller. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.
The problem, in real life
A long market lane has stalls in a row, and every stall sells just one thing: rice, ginger, chillies, onions, salt. Mummy's shopping list says rice, ginger, chillies. You will walk one continuous stretch of the lane, no jumping around, and that stretch must have every item on the list. Which stretch is the shortest? If the list says two packets of rice, the stretch needs two rice stalls.
| Real life | In code |
|---|---|
| The market lane | the string s |
| One stall | one character s[i] |
| Mummy's list | the string t |
| A stretch you walk | a window (substring) s[l..r] |
| The shortest stretch that buys everything | the minimum window |
Problem statement
Given strings s and t, return the shortest substring of s that contains every character of t with its count (if t has two a's, the window needs at least two). If there is no such window, return "". Constraints: 1 ≤ s.length, t.length ≤ 10⁵, English letters. (LeetCode guarantees the answer is unique.)
| s | t | answer |
|---|---|---|
"ADOBECODEBANC" |
"ABC" |
"BANC" |
"a" |
"a" |
"a" |
"a" |
"aa" |
"" (t needs two a's) |
"hello" |
"xyz" |
"" (no window) |
"baacbab" |
"aab" |
"baa" |
The tally: need[] and missing
How do we know a window covers the list? Keep a tally:
int[] need = new int[128]: for each character oft,need[c]++. 128 slots cover every ASCII character.- Adding a character
cto the window:need[c]--. A negative value means the window has extras (more than the list needs). missing= how many characters oftthe window still lacks. It starts att.length()and goes down only whenneed[c] > 0before the decrement (the character was still needed).missing == 0means the window is valid: it covers the list. One number to check, O(1), instead of comparing whole tallies.
Solution 1: brute force (restart at every index)
Start at every index i, make a fresh tally, walk right until missing hits 0. That is the shortest window starting at i; keep the best.
public class Main {
static String minWindow(String s, String t) {
String best = "";
for (int i = 0; i < s.length(); i++) {
int[] need = new int[128];
for (char c : t.toCharArray()) need[c]++;
int missing = t.length();
for (int j = i; j < s.length(); j++) {
if (need[s.charAt(j)]-- > 0) missing--;
if (missing == 0) {
if (best.isEmpty() || j - i + 1 < best.length())
best = s.substring(i, j + 1);
break;
}
}
}
return best;
}
public static void main(String[] args) {
System.out.println(minWindow("ADOBECODEBANC", "ABC"));
}
}
Output:
BANC
On a big lane (2 lakh characters cycling through a..t, with "xyz" only at the very end):
public class Main {
static String minWindow(String s, String t) {
String best = "";
for (int i = 0; i < s.length(); i++) {
int[] need = new int[128];
for (char c : t.toCharArray()) need[c]++;
int missing = t.length();
for (int j = i; j < s.length(); j++) {
if (need[s.charAt(j)]-- > 0) missing--;
if (missing == 0) {
if (best.isEmpty() || j - i + 1 < best.length())
best = s.substring(i, j + 1);
break;
}
}
}
return best;
}
public static void main(String[] args) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 200000; i++) sb.append((char) ('a' + i % 20));
String s = sb + "xyz";
System.out.println(minWindow(s, "xyz"));
}
}
Result: Time Limit Exceeded. Every start walks almost the whole lane again: about n²/2 = 2 × 10¹⁰ steps.
Why it is slow, and the key insight
- n starting points × a walk of up to n = O(n²).
- Moving from start
itoi + 1, we throw away the whole tally and re-buy everything, although the two windows share almost every character. - Keep the window, just drop its first character. If
s[l..r]is valid, thens[l..r']for any laterr'is valid too, and longer. So once we have recorded the best window starting atl,lcan never give anything better: drop it forever and movelright.
The three moves:
- Grow: add
s[r]to the window (update the tally),r++. - Record: while the window is valid (
missing == 0), comparer - l + 1with the best. - Shrink: drop
s[l](give it back to the tally),l++. If it was needed,missinggoes up and the window is broken; go back to growing.
Both l and r only move right, so each moves at most n times: O(n).
Dry run: s = "ADOBECODEBANC", t = "ABC"
| Step | Window s[l..r] |
missing | Best |
|---|---|---|---|
| Start: need A1 B1 C1 | (empty) | 3 | - |
| Grow to r = 5 | ADOBEC (0..5) |
0 | ADOBEC (6) |
| Drop A at 0 | DOBEC (1..5) |
1 | 6 |
| Grow to r = 10 (an A) | DOBECODEBA (1..10) |
0 | 10 > 6, keep 6 |
| Drop D, O, B, E (spare: another B at 9), then C at 5 | ODEBA (6..10) |
1 | 6 |
| Grow to r = 12 (a C) | ODEBANC (6..12) |
0 | 7 > 6, keep 6 |
Drop O (DEBANC, 6), drop D (EBANC, 5), drop E (BANC, 4) |
BANC (9..12) |
0 | BANC (4) |
| Drop B at 9 | ANC (10..12) |
1 | end of s |
Answer: BANC. Every character entered the window once and left at most once.
Solution 2: the sliding window
public class Main {
static String minWindow(String s, String t) {
int[] need = new int[128];
for (char c : t.toCharArray()) need[c]++;
int missing = t.length(), l = 0;
int start = 0, best = Integer.MAX_VALUE;
for (int r = 0; r < s.length(); r++) {
char c = s.charAt(r);
if (need[c] > 0) missing--;
need[c]--;
while (missing == 0) {
if (r - l + 1 < best) { best = r - l + 1; start = l; }
char d = s.charAt(l++);
need[d]++;
if (need[d] > 0) missing++;
}
}
if (best == Integer.MAX_VALUE) return "";
return s.substring(start, start + best);
}
public static void main(String[] args) {
System.out.println("[" + minWindow("ADOBECODEBANC", "ABC") + "]");
System.out.println("[" + minWindow("a", "a") + "]");
System.out.println("[" + minWindow("a", "aa") + "]");
System.out.println("[" + minWindow("hello", "xyz") + "]");
System.out.println("[" + minWindow("baacbab", "aab") + "]");
}
}
Output:
[BANC]
[a]
[]
[]
[baa]
The square brackets make an empty answer visible. "a"/"aa": t is longer than s, so missing never reaches 0. "hello"/"xyz": no window. "baacbab"/"aab": the duplicate a is counted, so the answer is baa (one b, two a's).
On the same 2-lakh lane:
public class Main {
static String minWindow(String s, String t) {
int[] need = new int[128];
for (char c : t.toCharArray()) need[c]++;
int missing = t.length(), l = 0;
int start = 0, best = Integer.MAX_VALUE;
for (int r = 0; r < s.length(); r++) {
char c = s.charAt(r);
if (need[c] > 0) missing--;
need[c]--;
while (missing == 0) {
if (r - l + 1 < best) { best = r - l + 1; start = l; }
char d = s.charAt(l++);
need[d]++;
if (need[d] > 0) missing++;
}
}
if (best == Integer.MAX_VALUE) return "";
return s.substring(start, start + best);
}
public static void main(String[] args) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 200000; i++) sb.append((char) ('a' + i % 20));
String s = sb + "xyz";
long t0 = System.nanoTime();
String w = minWindow(s, "xyz");
System.out.println(w + " " + (System.nanoTime() - t0) / 1000000 + " ms");
}
}
Output:
xyz 24 ms
(The exact milliseconds change from run to run.) About 4 lakh pointer moves instead of 2 × 10¹⁰.
The same solution in C++ and Python
#include <bits/stdc++.h>
using namespace std;
string minWindow(const string& s, const string& t) {
int need[128] = {0};
for (char c : t) need[(unsigned char)c]++;
int missing = t.size(), l = 0, start = 0, best = INT_MAX;
for (int r = 0; r < (int)s.size(); r++) {
unsigned char c = s[r];
if (need[c] > 0) missing--;
need[c]--;
while (missing == 0) {
if (r - l + 1 < best) { best = r - l + 1; start = l; }
unsigned char d = s[l++];
need[d]++;
if (need[d] > 0) missing++;
}
}
return best == INT_MAX ? "" : s.substr(start, best);
}
int main() {
cout << "[" << minWindow("ADOBECODEBANC", "ABC") << "]\n";
cout << "[" << minWindow("a", "a") << "]\n";
cout << "[" << minWindow("a", "aa") << "]\n";
cout << "[" << minWindow("hello", "xyz") << "]\n";
cout << "[" << minWindow("baacbab", "aab") << "]\n";
}
def min_window(s: str, t: str) -> str:
need = [0] * 128
for c in t:
need[ord(c)] += 1
missing, l, start, best = len(t), 0, 0, float("inf")
for r, ch in enumerate(s):
c = ord(ch)
if need[c] > 0:
missing -= 1
need[c] -= 1
while missing == 0:
if r - l + 1 < best:
best, start = r - l + 1, l
d = ord(s[l])
l += 1
need[d] += 1
if need[d] > 0:
missing += 1
return "" if best == float("inf") else s[start:start + best]
for s, t in [("ADOBECODEBANC", "ABC"), ("a", "a"), ("a", "aa"), ("hello", "xyz"), ("baacbab", "aab")]:
print("[" + min_window(s, t) + "]")
Both print the same five lines as the Java version: [BANC], [a], [], [], [baa]. (In C++, substr takes a start and a length; in Java, substring takes a start and an end index.)
Bug 1: if instead of while
Replace while (missing == 0) with if (missing == 0):
public class Main {
static String minWindow(String s, String t) {
int[] need = new int[128];
for (char c : t.toCharArray()) need[c]++;
int missing = t.length(), l = 0;
int start = 0, best = Integer.MAX_VALUE;
for (int r = 0; r < s.length(); r++) {
char c = s.charAt(r);
if (need[c] > 0) missing--;
need[c]--;
if (missing == 0) {
if (r - l + 1 < best) { best = r - l + 1; start = l; }
char d = s.charAt(l++);
need[d]++;
if (need[d] > 0) missing++;
}
}
if (best == Integer.MAX_VALUE) return "";
return s.substring(start, start + best);
}
public static void main(String[] args) {
System.out.println(minWindow("ADOBECODEBANC", "ABC"));
}
}
Output:
ADOBEC
Wrong: the answer is BANC. With if, the window shrinks by only one character each time r moves. Near the end it needed to lose several characters at once, l crawled forward one step per r, and r reached the end of the string first.
Bug 2: substring(start, best)
public class Main {
static String minWindow(String s, String t) {
int[] need = new int[128];
for (char c : t.toCharArray()) need[c]++;
int missing = t.length(), l = 0;
int start = 0, best = Integer.MAX_VALUE;
for (int r = 0; r < s.length(); r++) {
char c = s.charAt(r);
if (need[c] > 0) missing--;
need[c]--;
while (missing == 0) {
if (r - l + 1 < best) { best = r - l + 1; start = l; }
char d = s.charAt(l++);
need[d]++;
if (need[d] > 0) missing++;
}
}
if (best == Integer.MAX_VALUE) return "";
return s.substring(start, best);
}
public static void main(String[] args) {
System.out.println(minWindow("ADOBECODEBANC", "ABC"));
}
}
Exception in thread "main" java.lang.StringIndexOutOfBoundsException: Range [9, 4) out of bounds for length 13
at java.base/jdk.internal.util.Preconditions$1.apply(Preconditions.java:55)
...
at java.base/java.lang.String.substring(String.java:2823)
at Main.minWindow(Main.java:21)
at Main.main(Main.java:24)
Java's substring(begin, end) takes an end index (exclusive), not a length. Start 9, length 4 → substring(9, 13).
Complexity
| Approach | Time | Extra space | n = 2 × 10⁵ |
|---|---|---|---|
| Brute force (restart at every index) | O(n² + n·m) | O(1) (a 128-int tally) | Time Limit Exceeded |
| Sliding window | O(n + m) | O(1) (a 128-int tally) | milliseconds |
Here n = s.length() and m = t.length(). For arbitrary Unicode characters use a HashMap<Character, Integer>; space becomes O(k) for k distinct characters.
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
if (missing == 0) to shrink |
ADOBEC (answer is BANC) |
shrinks only one step per r |
while (missing == 0) |
s.substring(start, best) |
StringIndexOutOfBoundsException: Range [9, 4) out of bounds for length 13 |
substring takes an end index |
s.substring(start, start + best) |
A HashSet of t's letters |
minWindow("a", "aa") gives "a" |
a set forgets duplicates | count with int[] need |
missing-- whenever c is in t |
minWindow("aaab", "ab") gives "a" (no b!) |
extra a's are counted as needed | decrement only if need[c] > 0 |
best starting at 0 |
always "" |
no window is shorter than 0 | start at Integer.MAX_VALUE |
Mini project: the shopping-route finder
Use the same idea with whole words and a HashMap (any items, not just ASCII letters): print which stalls to walk.
import java.util.*;
public class Main {
public static void main(String[] args) {
String[] lane = {"onion", "rice", "tea", "ginger", "salt", "chilli", "rice", "ginger", "onion", "chilli"};
String[] list = {"rice", "ginger", "chilli"};
Map<String, Integer> need = new HashMap<>();
for (String x : list) need.merge(x, 1, Integer::sum);
int missing = list.length, l = 0, start = 0, best = Integer.MAX_VALUE;
for (int r = 0; r < lane.length; r++) {
if (need.merge(lane[r], -1, Integer::sum) >= 0) missing--;
while (missing == 0) {
if (r - l + 1 < best) { best = r - l + 1; start = l; }
if (need.merge(lane[l++], 1, Integer::sum) > 0) missing++;
}
}
if (best == Integer.MAX_VALUE) System.out.println("Cannot buy everything in one stretch");
else System.out.println("Walk stalls " + start + " to " + (start + best - 1) + ": "
+ String.join(", ", Arrays.copyOfRange(lane, start, start + best)));
}
}
Output:
Walk stalls 5 to 7: chilli, rice, ginger
HashMap.merge(key, delta, Integer::sum) adds delta and returns the new count, so >= 0 after a -1 means the item was still needed.
Practice
- Change
minWindowto return the window's start index and length as anint[].
Solution
Return best == Integer.MAX_VALUE ? new int[]{-1, 0} : new int[]{start, best};. For the example: [9, 4].
- Permutation in String (LeetCode 567): does
s2contain some ordering ofs1?
Solution
A window of fixed size k = s1.length(): add s2[r], and once r ≥ k remove s2[r - k]. The same tally and missing counter; the answer is true the moment missing == 0. Both functions below were run:
import java.util.*;
public class Main {
// Permutation in String: does s2 contain some ordering of s1?
static boolean checkInclusion(String s1, String s2) {
int[] need = new int[128];
for (char c : s1.toCharArray()) need[c]++;
int missing = s1.length(), k = s1.length();
for (int r = 0; r < s2.length(); r++) {
if (need[s2.charAt(r)]-- > 0) missing--;
if (r >= k && ++need[s2.charAt(r - k)] > 0) missing++;
if (missing == 0) return true;
}
return false;
}
// Find All Anagrams: every start index of an anagram of p in s
static List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
int[] need = new int[128];
for (char c : p.toCharArray()) need[c]++;
int missing = p.length(), k = p.length();
for (int r = 0; r < s.length(); r++) {
if (need[s.charAt(r)]-- > 0) missing--;
if (r >= k && ++need[s.charAt(r - k)] > 0) missing++;
if (missing == 0) res.add(r - k + 1);
}
return res;
}
public static void main(String[] args) {
System.out.println(checkInclusion("ab", "eidbaooo"));
System.out.println(checkInclusion("ab", "eidboaoo"));
System.out.println(findAnagrams("cbaebabacd", "abc"));
System.out.println(findAnagrams("abab", "ab"));
}
}
Output:
true
false
[0, 6]
[0, 1, 2]
- Find All Anagrams in a String (LeetCode 438): every start index of an anagram of
pins.
Solution
The same fixed window as question 2, but instead of returning, record r - k + 1 every time missing == 0 (see findAnagrams above: [0, 6] for "cbaebabacd"/"abc").
- Why can't the window ever need to move
lbackwards?
Solution
If s[l..r] is valid, every longer window s[l..r'] is valid too, so the best window starting at l is the first valid one; after recording it, l is useless. And if s[l..r] is not valid, no window s[l'..r] with l' > l is valid either, so r must grow.
Quick quiz
What does minWindow("CABWEFGEWCWAEFGCF", "CAE") return?
- CWAE
- CABWE
- AEFGC
- WAEFGC
Answer
CWAE (we ran it). CABWE (indexes 0..4) and AEFGC (11..15) are valid but 5 long; CWAE (9..12) is 4 long and has C, A and E. Nothing shorter has all three.
Interview questions
- How do you check in O(1) that a window covers t? Keep
need[c]counts and amissingcounter that changes only when a still-needed character enters or a needed character leaves. - Why is the sliding window O(n)?
rmoves n times andlmoves at most n times in total; each move is O(1). - What changes for "longest" instead of "shortest" windows? Shrink while the window is invalid and record after the loop (episode 9); for "shortest", shrink while it is valid and record inside the loop.
- How do you handle duplicates in t? Counts, not a set:
need['a'] = 2for"aa". - Unicode input? Replace
int[128]with aHashMap<Character, Integer>.
Glossary
| Term | Meaning |
|---|---|
| Substring | A continuous piece of a string, e.g. "BANC" in "ADOBECODEBANC" |
| Window | The substring between two indexes l and r, s[l..r], that the algorithm is looking at |
| Valid window | A window that contains every character of t, with counts |
| Sliding window | A technique where a window moves over the input by growing on one end and shrinking on the other, never going back |
| Frequency count / tally | How many times each character appears, kept in an array like int[] need = new int[128] |
need[c] |
How many more c's the window still needs; negative means extras |
missing |
How many characters of t the window still lacks; 0 means valid |
| ASCII | The 128 basic characters (letters, digits, symbols), numbered 0-127, so need['A'] is need[65] |
| Two pointers | Two indexes (l, r) moved through the data under simple rules |
Integer.MAX_VALUE |
The largest int, 2,147,483,647, used as "nothing found yet" |
substring(begin, end) |
Java's way to cut a string: from begin up to, not including, end |
| Fixed-size window | A window whose length never changes; used for anagram problems |
| Time Limit Exceeded (TLE) | The judge stopped the program because it ran longer than allowed (8 s here) |
Summary
- A tally (
need[]) plus onemissingnumber tells, in O(1), whether a window coverst. - Brute force restarts at every index: O(n²), Time Limit Exceeded on big inputs.
- Sliding window: grow
runtil valid, shrinklwhile valid, record inside the loop. - Both pointers only move forward: O(n + m) time, O(1) space.
- Duplicates need counts, not a set;
substringtakes an end index.
Next episode: Sliding Window Maximum: the monotonic deque (hard).