SyntaxPilot
Courses/DSA and Coding Problems/Lesson 10
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 10 of 90

Minimum Window Substring (hard)

queued

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 of t, need[c]++. 128 slots cover every ASCII character.
  • Adding a character c to the window: need[c]--. A negative value means the window has extras (more than the list needs).
  • missing = how many characters of t the window still lacks. It starts at t.length() and goes down only when need[c] > 0 before the decrement (the character was still needed).
  • missing == 0 means 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 i to i + 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, then s[l..r'] for any later r' is valid too, and longer. So once we have recorded the best window starting at l, l can never give anything better: drop it forever and move l right.

The three moves:

  1. Grow: add s[r] to the window (update the tally), r++.
  2. Record: while the window is valid (missing == 0), compare r - l + 1 with the best.
  3. Shrink: drop s[l] (give it back to the tally), l++. If it was needed, missing goes 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

  1. Change minWindow to return the window's start index and length as an int[].
Solution

Return best == Integer.MAX_VALUE ? new int[]{-1, 0} : new int[]{start, best};. For the example: [9, 4].

  1. Permutation in String (LeetCode 567): does s2 contain some ordering of s1?
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]
  1. Find All Anagrams in a String (LeetCode 438): every start index of an anagram of p in s.
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").

  1. Why can't the window ever need to move l backwards?
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

  1. How do you check in O(1) that a window covers t? Keep need[c] counts and a missing counter that changes only when a still-needed character enters or a needed character leaves.
  2. Why is the sliding window O(n)? r moves n times and l moves at most n times in total; each move is O(1).
  3. 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.
  4. How do you handle duplicates in t? Counts, not a set: need['a'] = 2 for "aa".
  5. Unicode input? Replace int[128] with a HashMap<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 one missing number tells, in O(1), whether a window covers t.
  • Brute force restarts at every index: O(n²), Time Limit Exceeded on big inputs.
  • Sliding window: grow r until valid, shrink l while valid, record inside the loop.
  • Both pointers only move forward: O(n + m) time, O(1) space.
  • Duplicates need counts, not a set; substring takes an end index.

Next episode: Sliding Window Maximum: the monotonic deque (hard).