Minimum window substring containing every character of a pattern

Given strings s and t, return the shortest substring of s that contains every character of t, with repeats counted. Return "" if there is none.

Interface

Unless you agree on a different interface with the interviewer, assume:

• min_window(s: str, t: str) -> str — if several windows are equally short, return the one that starts first. An empty t returns "".

Example

min_window("ADOBECODEBANC", "ABC")   ->  "BANC"
min_window("a", "aa")                ->  ""          # t needs two a's
min_window("aa", "aa")               ->  "aa"

Constraints

• 0 <= len(s), len(t) <= 10^5. Any characters, case-sensitive.
• Aim for O(len(s) + len(t)) time.

Clarifying questions

• Do repeated characters in t have to appear that many times?
• Is the match case-sensitive?
• Which window wins a tie?
• Return the substring or its indices?

What a strong answer covers

• A sliding window with a need count for t and a counter of how many distinct characters are fully covered.
• Grow the right end until the window covers t. Then shrink from the left while it still covers, recording the best window, and stop when a needed character falls short.
• O(len(s) + len(t)) time, O(alphabet) space, and why each pointer moves at most len(s) times.
• Tests: t longer than s, t with repeats, the answer at the very start or end, no answer.

Follow-ups

• The characters of t must appear in order (a subsequence), not just be present.
• Many queries t against the same long s.
• Return every minimal window.