# Minimum Window Substring

Write a function `minWindowSubstring`

that takes two strings `s`

and `t`

. The function should return the minimum window substring of `s`

such that every character in t (including duplicates) is included in the window. If no such window exists, return an empty string. The order of the characters in the target string `t`

does not need to match the order in the window.

#### Constraints

The length of string s and t will be between 1 and 10,000.

The strings will consist of English alphabetic characters and are case sensitive.

#### Examples

```
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window in s that contains every character in t is "BANC".
Input: s = "a", t = "a"
Output: "a"
Explanation: The minimum window in s that contains t is "a" itself.
```

#### Tips:

- Consider using two pointers to create a sliding window over
`s`

. - Use a hash map to keep track of the characters and their counts in
`t`

. - Expand and contract the window while updating a hash map for the window to find the minimum length substring that contains all characters of
`t`

.

### Solution

### What’s the Exact `Minimum Window Substring`

Problem?

The problem is to find the smallest substring in s that contains all the characters in t, including duplicates.

#### Steps to Understand the Minimum Window Substring Problem

Understand that you need to find a substring in s where all characters in t are present.

The order of characters from t in the substring doesn’t matter.

The challenge lies in optimizing the search to find the minimum length substring.

#### Examples

```
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Input: s = "a", t = "a"
Output: "a"
```

#### What Your Function Should Do?

The function minWindowSubstring should take two strings s and t and return the minimum window substring of s that contains every character of t.

#### How to Solve the `Minimum Window Substring`

Problem

- Use the sliding window technique with two pointers to traverse through s.
- Utilize a hash map to count the characters of t and another hash map to count characters in the current window of s.
- Expand and contract the window and update the counts in the hash map to find the minimum length substring that contains all characters of t.

#### Example Code Solution

```
from collections import Counter
def minWindowSubstring(s, t):
if not t or not s:
return ""
dict_t = Counter(t)
required = len(dict_t)
l, r = 0, 0
formed = 0
window_counts = {}
ans = float("inf"), None, None
while r < len(s):
character = s[r]
window_counts[character] = window_counts.get(character, 0) + 1
if character in dict_t and window_counts[character] == dict_t[character]:
formed += 1
while l <= r and formed == required:
character = s[l]
if r - l + 1 < ans[0]:
ans = (r - l + 1, l, r)
window_counts[character] -= 1
if character in dict_t and window_counts[character] < dict_t[character]:
formed -= 1
l += 1
r += 1
return "" if ans[0] == float("inf") else s[ans[1]:ans[2] + 1]
```

#### Example Usage

```
print(minWindowSubstring("ADOBECODEBANC", "ABC")) # Output: "BANC"
print(minWindowSubstring("a", "a")) # Output: "a"
```

#### How this Code Works:

- The function uses two pointers (l and r) to create a sliding window over
`s`

. - It uses two hash maps:
`dict_t`

for the count of each character in t and window_counts for the count of each character in the current window of`s`

. - The window is expanded by moving r and updated window_counts accordingly. When all characters from t are found in the window, the function tries to contract the window by moving
`l`

to find the minimum length substring. - The ans tuple keeps track of the length and starting and ending indices of the minimum window found.

#### Time Complexity

The time complexity of this solution is `O(S + T)`

, where `S`

is the length of string `s`

and `T`

is the length of string t. This is because the function iterates through each character of s and t at most twice - once by the right pointer and once by the left pointer. The space complexity is `O(S + T)`

for the hash maps used to store character counts.