# Minimum Window Substring

##### December 27, 2023

## Problem #

Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string.

## Solution #

The Python function `min_window`

successfully finds the minimum window in the string `s`

that contains all the characters of the string `t`

. In the provided example with `s = "ADOBECODEBANC"`

and `t = "ABC"`

, the function returned `"BANC"`

as the smallest substring of `s`

that includes all the characters in `t`

.

Here’s the code for the `min_window`

function:

```
def min_window(s, t):
"""
Find the minimum window in s which will contain all the characters in t.
If no such window exists, return an empty string.
:param s: Source string
:param t: Target string
:return: Minimum window substring or empty string
"""
if not t or not s:
return ""
dict_t = collections.Counter(t)
required = len(dict_t)
l, r = 0, 0
formed = 0
window_counts = collections.Counter()
ans = float("inf"), None, None
while r < len(s):
character = s[r]
window_counts[character] += 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
s = "ADOBECODEBANC"
t = "ABC"
min_window(s, t)
```

This function works by using a sliding window technique to find the smallest substring in `s`

that contains all the characters of `t`

. It expands the window by moving the right pointer and shrinks it by moving the left pointer while keeping track of the number of required characters that are currently in the window. When the window fulfills the requirement (contains all characters from `t`

), it updates the answer with the minimum window size found so far.

## Solution Analysis #

The `min_window`

function is designed to find the smallest substring in a given string `s`

that contains all the characters of another string `t`

. It uses the sliding window technique, a common approach for solving substring search problems. Let’s break down the code into its main components:

### 1. Initial Checks and Setup #

- The function first checks if either
`s`

or`t`

is empty. If so, it returns an empty string, as there can be no valid window. `dict_t`

is a dictionary that stores the count of each character in`t`

. This helps to keep track of what characters and how many of each we need to find in`s`

.`required`

is the number of unique characters in`t`

that we need to find in`s`

.

### 2. Sliding Window Initialization #

- Two pointers,
`l`

(left) and`r`

(right), are initialized to 0. They represent the bounds of the sliding window. `formed`

keeps track of how many unique characters from`t`

have been found in the current window in the correct frequency.`window_counts`

is a dictionary to store the count of each character in the current window.`ans`

is a tuple that will eventually store the length of the minimum window, and the left and right indices of this window in`s`

.

### 3. Sliding Window Expansion #

- The outer
`while`

loop (controlled by`r < len(s)`

) is used to expand the window by moving the right pointer`r`

. For each character added to the window, its count is updated in`window_counts`

. - If a character from
`s`

is also in`t`

and its count matches the required count in`t`

,`formed`

is incremented.

### 4. Sliding Window Contraction #

- The inner
`while`

loop is executed when`formed`

equals`required`

, meaning the current window contains all the necessary characters from`t`

. - Inside this loop, the function checks if the current window length is smaller than the smallest found so far. If it is, it updates
`ans`

with the new window length and indices. - Then, the function attempts to contract the window by increasing the left pointer
`l`

and adjusting the counts in`window_counts`

. If the window no longer contains all characters from`t`

in the required frequency,`formed`

is decremented.

### 5. Result #

- The function returns the smallest window found. If no such window is found (
`ans[0]`

remains`float("inf")`

), an empty string is returned.

### Example Usage #

- The example uses
`s = "ADOBECODEBANC"`

and`t = "ABC"`

. The function finds “BANC” as the smallest substring of`s`

containing all characters of`t`

.

This code is efficient for substring search problems, as it dynamically adjusts the window size and only iterates through the string `s`

once, achieving good time complexity.