Minimum Window Substring

Return the shortest substring of s that contains every character of t, including duplicates. Return an empty string if there is none.

A way to picture it

You're on a scavenger hunt down a street of shops, and t is your shopping list. Walk forward buying things until your bag has everything. Then, from the back of your route, hand back anything you don't need, making the trip as short as possible.

How to approach it

Expand R until the window covers every needed letter, then shrink L while it still does, recording the shortest window. Repeat until R reaches the end.

Example

Input: {"s":"ADOBECODEBANC","t":"ABC"}. Output: "BANC".

Complexity: O(|s| + |t|) time and O(k) space. Each index enters and leaves the window at most once.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.