Practice/Meta/Leetcode 76. Minimum Window Substring

Leetcode 76. Minimum Window Substring

CodingMust

Problem

You are given two strings: a source string s and a target string t. Your task is to find the shortest contiguous substring within s that contains every character from t, including duplicates. If multiple substrings of the same minimum length exist, return any one of them. If no such substring exists, return an empty string.

The substring must contain at least the same frequency of each character as appears in t. For example, if t contains two 'a's, the result substring must also contain at least two 'a's.

Requirements

1. Return the shortest substring of s that contains all characters from t with their required frequencies
2. If multiple minimum-length substrings exist, any valid answer is acceptable
3. If no valid substring exists, return an empty string ""
4. The solution should handle both uppercase and lowercase letters as distinct characters
5. Character order in the result substring does not need to match the order in t

Constraints

• 1 ≤ length of t ≤ length of s ≤ 100,000
• Both s and t consist of uppercase and lowercase English letters
• Target time complexity: O(m + n) where m and n are the lengths of s and t
• Target space complexity: O(k) where k is the number of unique characters

Examples

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" Explanation: The substring "BANC" contains A, B, and C. Other substrings like "ADOBEC" also work but are longer.

Example 2:

Input: s = "a", t = "aa" Output: "" Explanation: The source string only has one 'a', but we need two. No valid window exists.

Example 3:

Input: s = "aaabbbc", t = "aabc" Output: "aabbc" Explanation: We need at least 2 a's, 1 b, and 1 c. The shortest window is "aabbc" with length 5.