PPractick

The problem

A search engine highlights the shortest snippet of a document that contains every character of the query, with multiplicity (a query "AAB" needs two As and a B). Given s and t, return the minimum-length substring of s that contains all of t's characters, or "" if none exists. A sliding window with a "still missing" counter solves it in O(|s| + |t|). Extend right until nothing is missing, then shrink from the left as long as the window still covers t, recording the best window before each shrink breaks coverage.

Example: s = "ADOBECODEBANC", t = "ABC" → "BANC".

Function signature

string minWindow(const string& s, const string& t);  // "" if no window exists

Test cases

Input (s, t)	Output	Explanation
("ADOBECODEBANC", "ABC")	"BANC"
("a", "a")	"a"
("a", "aa")	""	Needs two a's
("ab", "b")	"b"
("aaflslflsldkalskaaa", "aaa")	"aaa"
("cabwefgewcwaefgcf", "cae")	"cwae"

(Confirm: duplicates in t must be matched with multiplicity; characters are ASCII; if several windows tie, return the leftmost.)

How interviewers phrase it

• "Given strings s and t, return the minimum window substring of s such that every character in t, including duplicates, is included" (LeetCode 76).

Clarifying questions to ask

1. Do duplicates in t matter? (Yes.)
2. What should happen if no window exists? (Return "".)
3. What's the character set? (ASCII: a 128-entry array.)

Follow-ups to expect

1. "How do you know the window covers t in O(1)?"
2. "When do you shrink?"
3. "Why is it O(n)?"
4. "How would you speed it up when t is tiny and s is huge?"
5. "Complexity?"

Related questions

• Longest Repeating Character Replacement Hard
• Longest Substring With At Most K Distinct Characters Hard
• Number of Substrings Containing All Three Characters Hard
• Minimum Window Subsequence Hard
• Isomorphic String Easy
• Check if two strings are anagram of each other Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in