Minimum Window Substring

Find the shortest substring of s that contains every character of t (including repeats: if t has two as, the window needs at least two as).

Input:

• line 1: s
• line 2: t

Output: the shortest such substring. If several have the same shortest length, print the leftmost one. If none exists, print NONE.

Constraints: 1 ≤ length of s, t ≤ 10⁵; uppercase and lowercase English letters (case matters).

Think about it: expand the right end until the window covers t, then shrink the left end as far as possible while it still covers t. Track how many characters are still "missing" so each step is O(1).