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.

class Solution {

public:

    string minWindow(string s, string t) {

        if (s.empty() || t.empty() || s.size() < t.size()) {

            return "";

        }

        map<char, int> mp;

        string ans;

        

        for (int i = 0; i < t.size(); i++) {

            mp[t[i]]++;

        }

        

        int st = 0, ed = 0, count = 0;

        

        while (ed < s.size()) {

            if (mp.find(s[ed]) != mp.end()) {

                mp[s[ed]]--;

                if (mp[s[ed]] >= 0) {

                    count++;

                }

                

                if (count == t.size()) {

                    while (st < s.size()) {

                        if (mp.find(s[st]) != mp.end() && mp[s[st]] >= 0) {

                            break;

                        } else if (mp.find(s[st]) != mp.end() && mp[s[st]] < 0) {

                            mp[s[st]]++;

                        }

                        st++;

                    }

                    string tmp = s.substr(st, ed - st + 1);

                    if (ans.empty()) {

                        ans = tmp;

                    } else if (tmp.size() < ans.size()) {

                        ans = tmp;

                    }

                }

            }

            ed++;

        }

        return ans;

    }

};

============ Efficient one =========

vector<int> letterCnt(128,0); int left = 0, cnt = 0, minLeft = -1, minLen = INT_MAX; for(char c:t) letterCnt[c]++; for(int i=0;i<s.size();i++){ if(--letterCnt[s[i]]>=0) cnt++; while(cnt == t.size()){ if(minLen > i-left+1){ minLen = i-left+1; minLeft = left; } if(++letterCnt[s[left]]>0) cnt--; left++; } } return minLeft == -1 ? "":s.substr(minLeft,minLen);

============== Another =======

class Solution { public: string minWindow(string s, string t) { map<char, int> mp; int count = 0; int left = 0, right = 0; int finalLeft = -1, finalRight = -1; int diff = INT_MAX; if (s.empty() || t.empty()) { return ""; } for (auto ch : t) { mp[ch]++; } while (right < s.size()) { if (mp.find(s[right]) == mp.end()) { right++; continue; } if (mp[s[right]] > 0) { count++; } mp[s[right]]--; while (count == t.size() && left < s.size()) { if (mp.find(s[left]) == mp.end()) { left++; continue; } int ans = right - left + 1; if (ans <= diff) { diff = ans; finalLeft = left; finalRight = right; } if (mp[s[left]] < 0) { mp[s[left]]++; left++; } else { break; } } right++; } if (finalLeft >= 0) { return s.substr(finalLeft, finalRight - finalLeft + 1); } return ""; } };