✅ Minimum Window Substring || Using Map w/ Explanation || C++ | Python | Java
IDEA\nThe solution is a bit intuitive. We keep expanding the window by moving the right pointer. When the window has all the desired characters, we contract (if
**IDEA**\nThe solution is a bit intuitive. We keep expanding the window by moving the right pointer. When the window has all the desired characters, we contract (if possible) and save the smallest window till now.\n`The answer is the smallest desirable window.`\n\n**EXAMPLE**\nFor eg. `S = "ABAACBAB" T = "ABC"`. Then our answer window is `"ACB"` and shown below is one of the possible desirable windows.\n![image](https://assets.leetcode.com/users/images/aa5e8ecb-faa5-4542-ba85-4c3c0b986b8d_1629012971.6332936.png)\n\n**ALGORITHM**\n*BASE CASE-*\nIf either s or t is null then we can\u2019t find any common window between them.\n\n*ELSE-*\n* We start with two pointers, `leftleft` and `rightright` initially pointing to the first element of the string SS.\n* We use the `rightright pointer` to expand the window until we get a desirable window i.e. a window that contains all of the characters of TT.\n* Once we have a window with all the characters, we can move the left pointer ahead one by one. \n\t* \tIf the window is still a desirable one we keep on updating the minimum window size.\n\t* \tIf the window is not desirable any more, we repeat step 2 onwards.\n\n**SOLUTION**\n`In C++`\n```\nclass Solution {\npublic:\n    string minWindow(string s, string t) {\n       unordered_map<char,int> mp;\n        for(auto ch:t)\n        {\n            mp[ch]++;\n        }\n        int dist=mp.size() ;\n        unordered_map<char,int> window;\n        int count = 0 , ll = 0 , rr = 0 ;\n        int l = 0 , r = 0 , ans = INT_MAX ;\n        while(r<s.length())\n        {\n            window[s[r]]++ ;\n            if(mp.count(s[r]) and mp[s[r]]==window[s[r]])\n            {\n                    count++;\n            }\n            r++;\n            while(count == dist and l < r)\n            {\n                if(ans > r-l)\n                {\n                    ans= r - l ;\n                    ll = l ;\n                    rr = r ;\n                }\n                window[s[l]]-- ;\n                if(mp.count(s[l]) and window[s[l]] < mp[s[l]])\n                {\n                        count--;\n                }\n                l++;\n            }\n        }\n        return s.substr(ll,rr-ll);\n    }\n};\n```\n`In Python`\n```\nclass Solution(object):\n    def minWindow(self, s, t):\n        """\n        :type s: str\n        :type t: str\n        :rtype: str\n        """\n        if not t or not s:\n            return ""\n\n        dict_t = Counter(t)\n        required = len(dict_t)\n        l, r = 0, 0\n        formed = 0\n        window_counts = {}\n        ans = float("inf"), None, None\n        while r < len(s):\n            character = s[r]\n            window_counts[character] = window_counts.get(character, 0) + 1\n            if character in dict_t and window_counts[character] == dict_t[character]:\n                formed += 1\n            while l <= r and formed == required:\n                character = s[l]\n\n                # Save the smallest window until now.\n                if r - l + 1 < ans[0]:\n                    ans = (r - l + 1, l, r)\n\n                window_counts[character] -= 1\n                if character in dict_t and window_counts[character] < dict_t[character]:\n                    formed -= 1\n                l += 1    \n\n            r += 1    \n        return "" if ans[0] == float("inf") else s[ans[1] : ans[2] + 1]\n\n```\n`In JAVA`\n```\nclass Solution {\n    public String minWindow(String s, String t) {\n        if(s==null || t==null)\n        {\n            return "";\n        }\n        HashMap<Character,Integer> map = new HashMap<Character,Integer>();\n        for(char c : t.toCharArray())\n        {\n            if(map.containsKey(c))\n            {\n                map.put(c,map.get(c)+1);\n            }\n            else\n            {\n                map.put(c,1);\n            }\n        }\n        int left = 0 , minLeft = 0, minLen = s.length() + 1 ;\n        int count = 0;\n        for(int right = 0; right < s.length(); right++)\n        {\n            if(map.containsKey(s.charAt(right)))\n            {\n                map.put(s.charAt(right),map.get(s.charAt(right))-1);\n                if(map.get(s.charAt(right)) >= 0)\n                {\n                    count ++;\n                }\n                while(count == t.length())\n                {\n                    if(right-left+1 < minLen)\n                    {\n                        minLeft = left;\n                        minLen = right-left+1;\n                    }\n                    if(map.containsKey(s.charAt(left)))\n                    {\n                        map.put(s.charAt(left),map.get(s.charAt(left))+1);\n                        if(map.get(s.charAt(left)) > 0)\n                        {\n                            count --;\n                        }\n                    }\n                    left++ ;\n                }\n            }\n        }\n        return minLen > s.length() ? "" : s.substring(minLeft,minLeft+minLen);\n    }\n}\n```\n
[]