> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/strings/17.-minimum-window-substring.md).

# 18. Minimum Window Substring

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 `""`*.

**Note** that If there is such a window, it is guaranteed that there will always be only one unique minimum window in `s`.

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

Example 2:
Input: s = "a", t = "a"
Output: "a"
```

## Solution: (Sliding Window + Hash Maps)

**Algorithm**

1. We start with two pointers, left and right initially pointing to the first element of the string S.
2. We use the right pointer to expand the window until we get a desirable window i.e. a window that contains all of the characters of T.
3. Once we have a window with all the characters, we can move the left pointer ahead one by one. If the window is still a desirable one we keep on updating the minimum window size.
4. If the window is not desirable any more, we repeat step 2 onwards.

![](https://leetcode.com/problems/minimum-window-substring/Figures/76/76_Minimum_Window_Substring_2.png)

The above steps are repeated until we have looked at all the windows. The smallest window is returned

.![](https://leetcode.com/problems/minimum-window-substring/Figures/76/76_Minimum_Window_Substring_3.png)

```cpp
class Solution
{
public:
    string minWindow(string s, string t)
    {

        int minLen = INT_MAX;

        unordered_map<char, int> tc;
        unordered_map<char, int> sc;

        string res = "";

        for (int i = 0; i < t.length(); i++)
        {
            tc[t[i]]++;
        }

        int start = 0;
        int i = 0;
        int count = 0;

        while (i < s.length())
        {
            if (tc.find(s[i]) != tc.end())
            {
                int val = tc[s[i]];

                int sameVal = sc[s[i]];
                if (sameVal < val)
                {
                    count++;
                }
                sc[s[i]]++;
            }

            while (count >= t.length())
            {
                if (i - start + 1 < minLen)
                {
                    res = s.substr(start, i - start + 1);
                    minLen = i - start + 1;
                }

                if (tc.find(s[start]) != tc.end())
                {
                    int val = tc[s[start]];

                    int sameVal = sc[s[start]];
                    if (sameVal <= val)
                    {
                        count--;
                    }
                    sc[s[start]]--;
                }
                start++;
            }

            i++;
        }
        return res;
    }
};
```

**Time Complexity: O(S + T)**\
**Space Complexity: O(S + T)**