Brute force to Optimal | Sliding Window | C++
Brute Force\n\nclass Solution {\n    bool check(unordered_map<char, int> &mp, unordered_map<char, int> &m) {\n        if(m.size() < mp.size()) return false;\n  
# Brute Force\n```\nclass Solution {\n    bool check(unordered_map<char, int> &mp, unordered_map<char, int> &m) {\n        if(m.size() < mp.size()) return false;\n        for(auto i : m) {\n            if(i.second < mp[i.first]) return false;\n        }\n        return true;\n    }\npublic:\n    string minWindow(string s, string t) {\n        unordered_map<char, int> mp, m;\n        for(char c : t) mp[c]++;\n\n        int i = 0, d = INT_MAX;\n        string ans;\n        for(int j=0; j<s.size(); j++) {\n            if(mp.find(s[j]) != mp.end()) m[s[j]]++;\n            while(check(mp, m)) {\n                if(j - i + 1 < d) d = j - i + 1, ans = s.substr(i, j - i + 1);\n                if(m.find(s[i]) != m.end()) m[s[i]]--;\n                i++;\n            }\n        }\n        return ans;\n    }\n};\n```\n\n# Optimal\n```\nclass Solution {\npublic:\n    string minWindow(string s, string t) {\n        unordered_map<char, int> m;\n        for(char c : t) m[c]++;\n\n        int i = 0, d = INT_MAX, cnt = m.size();\n        string ans;\n        for(int j=0; j<s.size(); j++) {\n            if(m.find(s[j]) != m.end()) {\n                m[s[j]]--;\n                if(!m[s[j]]) cnt--;\n            }\n            while(!cnt) {\n                if(j - i + 1 < d) d = j - i + 1, ans = s.substr(i, j - i + 1);\n                if(m.find(s[i]) != m.end()) {\n                    m[s[i]]++;\n                    if(m[s[i]] > 0) cnt++;\n                }\n                i++;\n            }\n        }\n        return ans;\n    }\n};\n```\n\n\n
['Hash Table', 'Sliding Window', 'C++']