Given two strings s and t of lengths m and n respectively, 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 the empty string "".

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.

&nbsp;
Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.


Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.


Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.


&nbsp;
Constraints:


	m == s.length
	n == t.length
	1 &lt;= m, n&nbsp;&lt;= 105
	s and t consist of uppercase and lowercase English letters.


&nbsp;
Follow up: Could you find an algorithm that runs in O(m + n) time?
# Added on 2022-08-18 15:51:55.963915

var minWindow = function(s, t) {
    const tf = {}, sf = {};
    for(let c of t) {
        tf[c] = (tf[c] || 0) + 1;
    }
    let l = 0, r = 0, rs = t.length;
    let ml = -1, mr = -1;
    for(; r < s.length; r++) {
        const c = s[r];

        if(!tf[c]) continue;

        const sc = sf[c] || 0;
        sf[c] = sc + 1;
        if(sf[c] <= tf[c]) {
            rs--;
        }

        if(rs == 0) {
            while(true) {
                if(mr == -1 || mr - ml > r - l) {
                    [mr, ml] = [r, l];
                }

                const c = s[l];
                if(!tf[c]) {
                    l++;
                }
                else if(sf[c] - 1 < tf[c]) {
                    sf[c]--, l++, rs++;
                    break;
                } else {
                    sf[c]--;
                    l++;
                }
            }
        }
    }
    if(mr == -1) return '';
    return s.slice(ml, mr + 1);
};
class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> child = new HashMap<>();
        HashMap<Character, Integer> parent = new HashMap<>();

        int left = -1, right = -1, match = 0;
        String window = "";

        for(int i = 0; i < t.length(); i++){
            char c = t.charAt(i);
            child.put(c, child.getOrDefault(c, 0) + 1); //Child frequency map
            }

        while(true){
            boolean f1 = false, f2 = false;

            while(right < s.length() - 1 && match < t.length()){
                right++;
                char c = s.charAt(right);
                parent.put(c, parent.getOrDefault(c, 0) + 1); // Acquiring characters till
                if(parent.getOrDefault(c, 0) <= child.getOrDefault(c, 0)) // match count is equal
                    match++;

                f1 = true;
            }
            while(left < right && match == t.length()){
                String potstring = s.substring(left + 1, right + 1);
                if(window.length() == 0 || window.length() > potstring.length())
                    window = potstring; //Calculating length of window

                    left++;
                    char c = s.charAt(left);
                    parent.put(c, parent.getOrDefault(c, 0) - 1);
                    if(parent.get(c) == 0) //Releasing characters by
                        parent.remove(c); //left pointer for finding smallest window

                    if(parent.getOrDefault(c, 0) < child.getOrDefault(c, 0))
                        match--;

                 f2 = true;
            }

            if(f1 == false && f2 == false)
                break;
        }

        return window;
    }
}
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char,int> ump;
    for(auto i:t){
        ump[i]++;
    }

    int i =0,j =0,count =0;
    int ans =INT_MAX,answer =0;
    for (;j < s.size();j++)
    {
        if(ump[s[j]]>0) {
            count++;
         }
        ump[s[j]]--;
        if(count==t.size()){

            while (i < j && ump[s[i]]<0)
            {
                ump[s[i]]++;
                i++;
            }
            if(ans > j-i+1){
                ans  = j-i+1;
                answer = i;
            }
            ump[s[i]]++;
            i++;
            count--;
        }
    }
    return ans==INT_MAX?"":s.substr(answer,ans);
    }
};
var minWindow = function(s, t) {
    const tf = {}, sf = {};
    for(let c of t) {
        tf[c] = (tf[c] || 0) + 1;
    }
    let l = 0, r = 0, rs = t.length;
    let ml = -1, mr = -1;
    for(; r < s.length; r++) {
        const c = s[r];

        if(!tf[c]) continue;

        const sc = sf[c] || 0;
        sf[c] = sc + 1;
        if(sf[c] <= tf[c]) {
            rs--;
        }

        if(rs == 0) {
            while(true) {
                if(mr == -1 || mr - ml > r - l) {
                    [mr, ml] = [r, l];
                }

                const c = s[l];
                if(!tf[c]) {
                    l++;
                }
                else if(sf[c] - 1 < tf[c]) {
                    sf[c]--, l++, rs++;
                    break;
                } else {
                    sf[c]--;
                    l++;
                }
            }
        }
    }
    if(mr == -1) return '';
    return s.slice(ml, mr + 1);
};
Minimum Window Substring