✅🔥Sliding Window Approach with Explanation - C++/Java/Python
\n# Intuition\nIn this problem, we need to find the minimum window substring of string s that contains all characters from string t. We can use a sliding window
\n# Intuition\nIn this problem, we need to find the minimum window substring of string `s` that contains all characters from string `t`. We can use a sliding window approach to find the minimum window substring efficiently.\n\n# Approach 01\n1. Create an unordered_map `mp` to store the count of characters in string `t`.\n2. Initialize variables `ans`, `start`, and `count`.\n3. Use pointers `i` and `j` to iterate through string `s`.\n4. Decrement count of the current character in the map; if it becomes 0, decrement the `count` variable.\n5. Move pointer `i` to check if it is possible to remove more characters and get smaller substrings.\n6. Store the smaller length in `ans` and update the `start` variable.\n7. Add the current element to the map and increment the count if it becomes greater than 0.\n8. If `ans` has a length other than `INT_MAX`, return the substring from the `start` index to the length of `ans`; otherwise, return an empty string.\n\n# Complexity\n\n- Time complexity: The time complexity of this solution is O(m), where \'m\' is the length of string \'s\'. The algorithm iterates through the string once, and each iteration involves constant time operations.\n\n- Space complexity: The space complexity is O(n), where \'n\' is the length of string \'t\'. We use additional space for the unordered_map to store characters from \'t\'.\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    string minWindow(string s, string t) {\n        int m = s.size(), n = t.size();\n        unordered_map<char, int> mp;\n\n        int ans = INT_MAX;\n        int start = 0;\n\n        for (auto x : t)\n            mp[x]++;\n\n        int count = mp.size();\n\n        int i = 0, j = 0;\n\n        while (j < s.length()) {\n            mp[s[j]]--;\n            if (mp[s[j]] == 0)\n                count--;\n\n            if (count == 0) {\n                while (count == 0) {\n                    if (ans > j - i + 1) {\n                        ans = j - i + 1;\n                        start = i;\n                    }\n                    mp[s[i]]++;\n                    if (mp[s[i]] > 0)\n                        count++;\n\n                    i++;\n                }\n            }\n            j++;\n        }\n        if (ans != INT_MAX)\n            return s.substr(start, ans);\n        else\n            return "";\n    }\n};\n```\n```Java []\nclass Solution {\n    public String minWindow(String s, String t) {\n        int m = s.length(), n = t.length();\n        HashMap<Character, Integer> mp = new HashMap<>();\n\n        int ans = Integer.MAX_VALUE;\n        int start = 0;\n\n        for (char x : t.toCharArray())\n            mp.put(x, mp.getOrDefault(x, 0) + 1);\n\n        int count = mp.size();\n\n        int i = 0, j = 0;\n\n        while (j < s.length()) {\n            mp.put(s.charAt(j), mp.getOrDefault(s.charAt(j), 0) - 1);\n            if (mp.get(s.charAt(j)) == 0)\n                count--;\n\n            if (count == 0) {\n                while (count == 0) {\n                    if (ans > j - i + 1) {\n                        ans = j - i + 1;\n                        start = i;\n                    }\n                    mp.put(s.charAt(i), mp.getOrDefault(s.charAt(i), 0) + 1);\n                    if (mp.get(s.charAt(i)) > 0)\n                        count++;\n\n                    i++;\n                }\n            }\n            j++;\n        }\n        if (ans != Integer.MAX_VALUE)\n            return s.substring(start, start + ans);\n        else\n            return "";\n    }\n}\n```\n```python []\nclass Solution(object):\n    def minWindow(self, s, t):\n        m, n = len(s), len(t)\n        mp = {}\n\n        ans = float(\'inf\')\n        start = 0\n\n        for x in t:\n            mp[x] = mp.get(x, 0) + 1\n\n        count = len(mp)\n\n        i = 0\n        j = 0\n\n        while j < len(s):\n            mp[s[j]] = mp.get(s[j], 0) - 1\n            if mp[s[j]] == 0:\n                count -= 1\n\n            if count == 0:\n                while count == 0:\n                    if ans > j - i + 1:\n                        ans = j - i + 1\n                        start = i\n                    mp[s[i]] = mp.get(s[i], 0) + 1\n                    if mp[s[i]] > 0:\n                        count += 1\n\n                    i += 1\n            j += 1\n\n        if ans != float(\'inf\'):\n            return s[start:start + ans]\n        else:\n            return ""\n```\n\n\n---\n\n> **Please upvote this solution**\n>
['Two Pointers', 'Sliding Window', 'Python', 'C++', 'Java', 'Python3']