# Minimum Window Substring

## Question ([LC.76](https://leetcode.com/problems/minimum-window-substring/#/description))

> Given a string S and a string T, find 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 `""`.

## Example

```
I: S = "ADOBECODEBANC", T = "ABC"
O: "BANC"
```

Order doesn't matter as long as the window contains all the information.

## Analysis

We need a hash map to store all characters in T and their frequency. Then scan through S to find the minimum window that contains all the characters.

## Brute Force Approach

```
for i from 0 to len(S)
    for j from i to len(S)
        if (currentChars includes searchChars)
            break
        else
            update currentChars
            j++
    end for
    update min substring j-i+1
end for
```

## Sliding Window Approach

```
for i from 0 to n-1
    while (j < n && window does not contain query)
        extend the window
        j++
    end while

    if the current window contains query
        update window depending on the size

    shrink the window
end for
```

## Code

```java
public String minWindow(String text, String query) {
    if (text == null || query == null || query.length() == 0) {
        return "";
    }
    int n = text.length(), m = query.length();
    Map<Character, Integer> windowMap = new HashMap<>();
    Map<Character, Integer> queryMap = new HashMap<>();
    for (int i = 0; i < m; i++) {       
        Character newChar = query.charAt(i);
        addCharToMap(queryMap, newChar);
    }
    String minSubstring = "";
    int minWindowLen = Integer.MAX_VALUE;
    int j = 0;
    for (int i = 0; i < n; i++) {
        Character newChar = text.charAt(i);
        // extend
        while (j < n && !isContained(windowMap, queryMap)) {
            addCharToMap(windowMap, text.charAt(j));
            j++;
        }
        // current window
        if (isContained(windowMap, queryMap)) {
            if (j - i < minWindowLen) {
                minWindowLen = j - i;
                minSubstring = text.substring(i, j);
            }
        }
        // shrink
        removeCharFromMap(windowMap, newChar);
    }
    return minSubstring;
}

private void addCharToMap(Map<Character, Integer> map, Character newChar) {
    if (map.containsKey(newChar)) {
        map.put(newChar, map.get(newChar) + 1);
    } else {
        map.put(newChar, 1);
    }
}

private void removeCharFromMap(Map<Character, Integer> map, Character oldChar) {
    if (map.get(oldChar) != null && map.get(oldChar) > 0) {
        map.put(oldChar, map.get(oldChar) - 1);
    }
}

private boolean isContained(Map<Character, Integer> windowMap, Map<Character, Integer> queryMap) {
    for (Character qKey : queryMap.keySet()) {
        if (windowMap.get(qKey) == null || windowMap.get(qKey) < queryMap.get(qKey)) {
            return false;
        }
    }
    return true;
}
```

## Time & Space Complexity

Time O(n\*#chars + m) Space O(n) can be optimized to O(m) by using a counter instead of calling `isContained` function with two maps


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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://zedive.gitbook.io/project-l/part-1/basic_data_structure/array_and_string/two-pointers/window/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.