# 76. Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

  • If there is no such window in S that covers all characters in T, return the empty string "".
  • If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

# Solution

Approach 1: Sliding Window.

# Code (Python)

Approach 1:

import collections
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        needed = collections.Counter(t)
        letters_missing = len(needed)
        min_substring = s + s
        
        l = 0
        for r in range(len(s)):
            if s[r] in needed:
                needed[s[r]] -= 1
                if needed[s[r]] == 0:
                    letters_missing -= 1
            if letters_missing > 0:
                continue
            while l < r and (s[l] not in needed or needed[s[l]] < 0):
                if s[l] in needed:
                    needed[s[l]] += 1
                l += 1
            if r - l + 1 < len(min_substring):
                min_substring = s[l:r+1]
        
        return min_substring if len(min_substring) <= len(s) else ""

# Code (C++)

Approach 1:

// Sliding Window.
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char,int> umap;
        for (int i = 0; i < t.size(); ++i)
        {
            umap[t[i]]++;
        }
        int head = 0;
        int tail = 0;
        int count = t.size();
        int minResLen = s.size() + 1;
        string res = "";
        while (count == 0 || tail < s.size())
        {
            if (count == 0)
            {
                if (umap.find(s[head]) != umap.end())
                {
                    if (umap[s[head]] == 0)
                    {
                        count++;
                        if (tail - head < minResLen)
                        {
                            minResLen = tail - head;
                            res = s.substr(head, minResLen);
                        }
                    }
                    umap[s[head]]++;                    
                }
                head++;
            }
            else
            {
                if (umap.find(s[tail]) != umap.end())
                {
                    if (umap[s[tail]] > 0)
                        count--;
                    umap[s[tail]]--;
                }
                tail++;
            }
        }
        return res;
    }
};

// Optimized Sliding Window.
// This kind of scenario might happen when length of string T is way too small than the length of string S and string S consists of numerous characters which are not present in T.
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char,int> umap;
        for (int i = 0; i < t.size(); ++i)
        {
            umap[t[i]]++;
        }
        vector<pair<char,int>> filteredS;
        for (int i = 0; i < s.size(); ++i)
        {
            if (umap.find(s[i]) != umap.end())
                filteredS.push_back(make_pair(s[i], i));
        }
        int head = 0;
        int tail = 0;
        int count = t.size();
        int minResLen = s.size() + 1;
        string res = "";
        while (count == 0 || tail < filteredS.size())
        {
            if (count == 0)
            {
                if (umap[filteredS[head].first] == 0)
                {
                    count++;
                    int len = filteredS[tail-1].second - filteredS[head].second + 1;
                    if (len < minResLen)
                    {
                        minResLen = len;
                        res = s.substr(filteredS[head].second, minResLen);
                    }
                }
                umap[filteredS[head].first]++;
                head++;
            }
            else
            {
                if (umap[filteredS[tail].first] > 0)
                    count--;
                umap[filteredS[tail].first]--;
                tail++;
            }
        }
        return res;
    }
};