Minimum Window Substring

You are given two strings s and t. Find the shortest contiguous substring of s that contains every character of t, including repeated characters at least as many times as they occur in t. If no such substring exists, output an empty line. If several shortest substrings exist, output the one that starts first in s.

Input: The first line contains the string s. The second line contains the string t. Output: Print the shortest substring of s covering all characters of t (with required multiplicity), or print an empty line if no such substring exists.

1 <= |s|, |t| <= 10^5 s and t consist of uppercase and lowercase English letters.

If t is longer than s, or requires more of some character than s contains in total, no valid window can EVER exist - the missing-count simply never reaching zero correctly handles this impossible case automatically.

Find the shortest substring of one string that contains every character of another string, including repeats. Brute force: Check every possible substring directly, verifying it contains all of t's characters with the right counts - this costs O(n²) or worse, too slow for large strings. Optimised: A sliding window with a 'characters still missing' counter lets both the right-edge expansion and left-edge shrinking happen in a SINGLE combined linear pass - every character is added to the window and removed from it at most once across the whole algorithm, giving true O(n+m) total work despite looking like nested loops.

1. Build a required-count array for the characters in t, and track how many DISTINCT required characters are currently 'satisfied' inside the window. 2. Expand the window on the RIGHT until all requirements are satisfied, then greedily SHRINK from the LEFT as much as possible while it stays valid, recording the best window found. 3. Continue expanding and shrinking across the whole string; the smallest recorded window is the answer.

Time: O(|s| + |t|) - one pass to build t's requirement map, one combined expand/shrink pass over s. Space: O(|t| + alphabet size), for the frequency maps tracking what's needed and what's currently in the window.

Handle the case where t requires more copies of some character than s contains anywhere (no valid window exists, print an empty line), and the case where s itself is the only valid window.

This is one of the most famous 'hard' sliding window problems - be ready to clearly explain the 'missing count' technique rather than re-checking full frequency map equality at every step, which would be much slower.