Minimum Window Substring

Given two strings, s and t, find the smallest substring of s that contains all the characters of t, including duplicates. This problem is fundamental to string manipulation and pattern matching, with applications in text editors, search engines, and bioinformatics.

Problem Description

You are tasked with writing a function that takes two strings, s (the search string) and t (the target string), as input. Your goal is to identify the shortest contiguous substring within s that comprises all the characters present in t, respecting their frequencies. If no such substring exists in s, you should return an empty string.

Key Requirements:

• The substring must contain every character from t.
• The frequency of each character in the substring must be greater than or equal to its frequency in t.
• The substring must be contiguous (a single, unbroken sequence of characters within s).

Expected Behavior:

• If a valid substring is found, return the shortest one. If multiple shortest substrings exist, any one of them is acceptable.
• If no substring in s contains all characters of t with the required frequencies, return an empty string.

Edge Cases to Consider:

• s or t could be empty strings.
• t could contain characters not present in s.
• t could have duplicate characters that need to be matched.
• s could be shorter than t.

Examples

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The substring "BANC" is the shortest substring of "ADOBECODEBANC" that contains 'A', 'B', and 'C'.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string "a" is the smallest substring containing "a".

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: The string "a" does not contain two 'a's, so no valid substring exists.

Constraints

• 1 <= length of s, length of t <= 10^5
• s and t consist of English letters (both uppercase and lowercase).
• The time complexity of your solution should ideally be O(N), where N is the length of s.

Notes

Consider using a sliding window approach. You'll likely need to efficiently track character counts within the current window and compare them against the target character counts. Hash maps (or dictionaries) are often very useful for managing character frequencies. Think about how you can expand and shrink the window effectively to find the minimum valid substring.