Leetcode 76. Minimum Window Substring

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.

Hint 1: Sliding Window Technique Consider using two pointers to represent a window in the source string. Expand the right pointer to include characters, and contract the left pointer when you have a valid window. This allows you to explore all possible windows efficiently.

Hint 2: Character Frequency Tracking Use hash maps (dictionaries) to track the frequency of characters needed from the target string and the frequency of characters in your current window. You can also maintain a counter to track how many unique characters have met their required frequency.

Hint 3: Optimization Strategy When your window contains all required characters, try shrinking it from the left to find the minimum length. Only move the right pointer when the window becomes invalid. Keep track of the smallest valid window seen so far.

Full Solution `` Approach Explanation:

This solution uses the sliding window technique combined with frequency counting:

1. Initialization: Create a frequency map for the target string to know what characters and counts we need. Initialize two pointers (left and right) to represent our window.
2. Expand Phase: Move the right pointer to expand the window, adding characters to our window frequency map. Track when each unique character reaches its required frequency.
3. Contract Phase: Once all required characters are in the window with sufficient frequency, try shrinking from the left to find the minimum valid window. Update the result whenever we find a smaller valid window.
4. Tracking State: Use formed_chars to efficiently track when we have a valid window (all unique characters meet their frequency requirement) instead of comparing entire maps each time.

Time Complexity: O(m + n) where m is the length of s and n is the length of t. Each character in s is visited at most twice (once by right pointer, once by left pointer).

Space Complexity: O(k) where k is the number of unique characters in t (at most 52 for English letters, or 128 for ASCII). We store frequency maps for target and window characters.