# 76. Minimum Window Substring 🌐

**Difficulty**: `Hard` - **Tags**: `String`, `Sliding Window`, `Hash Table`

[LeetCode Problem Link](https://leetcode.com/problems/minimum-window-substring/)

## Problem Statement 📜

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 no such substring exists, return the empty string `""`.

## Examples 🌟

🔹 **Example 1:**

**Input:**

```python
s = "ADOBECODEBANC"
t = "ABC"
```

**Output:**

```
"BANC"
```

**Explanation:** The substring "BANC" is the smallest window in `s` that contains all the characters of `t`.

🔹 **Example 2:**

**Input:**

```python
s = "a"
t = "a"
```

**Output:**

```
"a"
```

**Explanation:** The entire string `s` is the minimum window.

🔹 **Example 3:**

**Input:**

```python
s = "a"
t = "aa"
```

**Output:**

```
""
```

**Explanation:** Both 'a's from `t` must be included in the window. Since `s` only has one 'a', there is no valid substring.

## Constraints ⚙️

* `1 <= m, n <= 10^5` where `m` is the length of `s` and `n` is the length of `t`.
* `s` and `t` consist of uppercase and lowercase English letters.

🤔 **Follow-up:** Could you solve the problem in `O(m + n)` time?

***

## Solution 💡

To solve this problem efficiently, we use the **Sliding Window** technique with two pointers and a frequency counter:

1. **Count Frequencies**:
   * Use a hash map to count the frequency of characters in `t`.
2. **Sliding Window**:
   * Expand the window by moving the right pointer until all characters in `t` are included in the current window.
   * Shrink the window from the left while maintaining the validity of the window, and update the result if the current window is smaller.
3. **Track Validity**:
   * Use a counter to track how many unique characters from `t` have been fully matched in the current window.
4. **Return Result**:
   * If no valid window is found, return `""`. Otherwise, return the smallest valid window.

### Java Solution

```java
import java.util.*;

public class Solution {
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) return "";

        Map<Character, Integer> tMap = new HashMap<>();
        for (char c : t.toCharArray()) {
            tMap.put(c, tMap.getOrDefault(c, 0) + 1);
        }

        int required = tMap.size();
        int left = 0, right = 0;
        int formed = 0;
        Map<Character, Integer> windowCounts = new HashMap<>();

        int[] ans = {-1, 0, 0}; // Length, Left, Right

        while (right < s.length()) {
            char c = s.charAt(right);
            windowCounts.put(c, windowCounts.getOrDefault(c, 0) + 1);

            if (tMap.containsKey(c) && windowCounts.get(c).intValue() == tMap.get(c).intValue()) {
                formed++;
            }

            while (left <= right && formed == required) {
                c = s.charAt(left);

                if (ans[0] == -1 || right - left + 1 < ans[0]) {
                    ans[0] = right - left + 1;
                    ans[1] = left;
                    ans[2] = right;
                }

                windowCounts.put(c, windowCounts.get(c) - 1);
                if (tMap.containsKey(c) && windowCounts.get(c).intValue() < tMap.get(c).intValue()) {
                    formed--;
                }

                left++;
            }

            right++;
        }

        return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
    }
}
```

***

## Time Complexity ⏳

* **O(m + n)**:
  * Traversing the string `s` takes `O(m)`.
  * Updating the frequency hash maps and shrinking the window is linear relative to the size of `s` and `t`.

## Space Complexity 💾

* **O(n)**:
  * Hash maps are used to store the frequencies of characters in `t` and the sliding window.

You can find the full solution [here](https://github.com/ChunhThanhDe/Leetcode-Top-Interview/blob/main/Topic%203%20Sliding%20Window/033%20Minimum%20Window%20Substring/Solution.java).


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://chunhthanhde.gitbook.io/leetcode-top-interview/topic-3-sliding-window/033-minimum-window-substring.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.