# Minimum Window Substring Leetcode Solution

## Minimum Window Substring Leetcode Problem :

Given two strings s and t of lengths m and n respectively, return the minimum window  substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string ” “.

The testcases will be generated such that the answer is unique.

## Minimum Window Substring Leetcode Problem Solution :

### Constraints :

• m == s.length
• n == t.length
• 1 <= m, n <= 105
• s and t consist of uppercase and lowercase English letters.

### Example 1:

• Input: s = “a”, t = “aa”
• Output: “”
• Explanation: Both ‘a’s from t must be included in the window.
Since the largest window of s only has one ‘a’, return empty string.

### Example 2:

• Input: s = “a”, t = “a”
• Output: “a”
• Explanation: The entire string s is the minimum window.

### Idea to solve:

The problem asks to find the minimum window in s that contains all the characters of t. One way to approach this problem is to use a sliding window technique. We can maintain a window that starts from the beginning of s and moves forward until it contains all the characters of t. Once we have such a window, we can try to shrink it by moving the window’s start pointer forward while still keeping all the characters of t in the window. This will give us the minimum window.

### Approach:

1. Check if s is shorter than t. If it is, there is no possible solution, and we return an empty string.
2. Create a frequency map of characters in t.
3. Initialize count, start, min_length, and min_start to 0.
4. Traverse the string s using the end pointer.
5. If the current character in s is present in the frequency map, increment the count.
6. Decrement the frequency of the current character in the frequency map.
7. If the count equals the length of t, it means we have found a window that contains all characters of t. Now we try to shrink the window by moving the start pointer forward until the window still contains all the characters of t.
8. If the length of the current window is smaller than the minimum length so far, update the minimum length and the minimum start.
9. Increment the frequency of the character at the start pointer and decrement the count.
10. Return the minimum window or an empty string if no window exists.

### Complexity:

• Time complexity: O(N), where N is the length of the string s.
We traverse the string s once.

• Space complexity: O(M), where M is the length of the string t.
We create a frequency map of characters in t.

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription