Minimum Window Substring

hardFREESliding WindowBlind 75

Given two strings s and t, 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 an empty string "".

Example

Input

ADOBECODEBANC
ABC

Output

BANC

Reasoning

Inputs: s = ADOBECODEBANC is the text to search (positions $0$ to $12$ ), and t = ABC lists the characters a window must contain (here one each).
Where the needed letters sit: A at positions $0$ and $10$ , B at $3$ and $9$ , C at $5$ and $12$ . A valid window covers at least one position from each pair.
Tight windows: only three valid windows cannot be trimmed at either end: ADOBEC (positions $0$ to $5$ , length $6$ ), CODEBA ( $5$ to $10$ , length $6$ ) and BANC ( $9$ to $12$ , length $12 - 9 + 1 = 4$ ). Every other valid window, e.g. EBANC (length $5$ ), contains one of them plus extra letters.
Output: the shortest is BANC, length $4$ . Dropping its first letter loses the B; dropping its last loses the C.
Duplicates matter: if t held two copies of A, BANC would no longer qualify. If no window covers t, the answer is the empty string.

Constraints

1 <= len(s), len(t) <= 10^5
s and t consist of uppercase and lowercase English letters

Learn this in

Two Pointers & Sliding WindowDSA Study Plan

More from Blind 75

Alien Dictionaryhard Clone Graphmedium Combination Summedium Word Search IIhard Merge K Sorted Listshard

Concept primer

Background Knowledge

The Minimum Window Substring problem involves finding the smallest substring of a given string s that contains all characters of another string t. This problem is a classic example of a sliding window problem, which is a common technique used in string and array problems. The sliding window approach involves creating a window that moves over the string, expanding or shrinking as necessary to meet certain conditions.

To understand this problem, it's essential to have a good grasp of string manipulation and hashing concepts. Hashing is particularly useful in this problem, as it allows us to efficiently keep track of the characters in the string t and their frequencies. We can use a hash map (or dictionary) to store the frequency of each character in t and then use this information to determine when we have found a valid window.

The problem also requires an understanding of optimization techniques, as we need to find the minimum window that satisfies the condition. This involves minimizing the size of the window while ensuring that it contains all the required characters. The greedy algorithm and two-pointer technique are also relevant concepts that can be applied to this problem.

Algorithm/Approach

The general approach to solving this problem involves using a sliding window technique, where we maintain a window of characters in the string s and expand or shrink it as necessary to include all characters of t. We can use a two-pointer technique to implement the sliding window, where one pointer represents the start of the window and the other represents the end.

Step-by-Step Strategy

To implement the solution, follow these steps:

Create a hash map to store the frequency of each character in the string t.
Initialize two pointers, left and right, to represent the start and end of the window.
Expand the window to the right by moving the right pointer and update the hash map with the characters in the window.
When the window contains all characters of t, try to shrink the window by moving the left pointer to the right and update the hash map accordingly.
Keep track of the minimum window size and the corresponding substring.

Common Pitfalls

When implementing the solution, watch out for the following:

Incorrectly updating the hash map when expanding or shrinking the window.
Failing to check if the window contains all characters of t before trying to shrink it.
Not handling edge cases, such as an empty string t or a string s that is shorter than t.

Time & Space Complexity

The expected time complexity for this problem is O( $n$ ), where $n$ is the length of the string s, since we need to iterate over the string to find the minimum window. The space complexity is O( $k$ ), where $k$ is the size of the character set, since we need to store the frequency of each character in the hash map. In the worst case, $k$ can be equal to $n$ , resulting in a space complexity of O( $n$ ).

solution.py

Python 3.13

Test results