Minimum Window Substring

Difficulty: Hard · Pattern: Sliding Window · Concept: General Coding (DSA) — Core Patterns to Drill

A significantly harder variant of Longest Run of Unique Characters: given a string s and a pattern t, find the shortest substring of s that contains every character of t, with multiplicity (if t has two as, the window needs at least two as too). Unlike the original problem's "no duplicates" condition, the window's validity here depends on a whole character-count budget being satisfied simultaneously.

Your task: implement min_window_substring(s, t). Return "" if no valid window exists.

Implement it yourself

assert min_window_substring("ADOBECODEBANC", "ABC") == "BANC"
assert min_window_substring("a", "a") == "a"
assert min_window_substring("a", "aa") == ""
assert min_window_substring("ab", "b") == "b"

Next: Search in a Rotated Sorted Array