🚀🚀 Beats 100% | Optimized Approach 🔥🔥 | Fully Explained 💎
Intuition \uD83E\uDD14:\nWe are given two strings, s and t, and we need to find the minimum window substring in s that contains all characters of t. To approach
### Intuition \uD83E\uDD14:\nWe are given two strings, `s` and `t`, and we need to find the minimum window substring in `s` that contains all characters of `t`. To approach this problem, we\'ll use two hash maps to keep track of characters in `s` and `t`, and then we\'ll use a sliding window technique to find the minimum window substring.\n\n### Approach \uD83D\uDE0E:\n1. Initialize variables: \n   - `len1` and `len2` store the lengths of strings `s` and `t` respectively.\n   - `start` indicates the start index of the current window.\n   - `ansIndex` holds the index of the minimum window substring.\n   - `ansLen` stores the length of the minimum window substring.\n2. Handle edge cases: If the length of `s` is less than the length of `t`, return an empty string.\n3. Create two unordered maps, `m1` and `m2`, to count the occurrences of characters in strings `s` and `t` respectively.\n4. Iterate through the characters of `s`:\n   - Increment the count of the current character in `m1`.\n   - Check if the count of the current character in `m1` is less than or equal to the count of the same character in `m2`. If so, increment `count`.\n   - Once `count` equals the length of `t`, it means we have found a window that contains all characters of `t`.\n   - Shrink the window by moving `start` forward while maintaining the window validity.\n   - Update the minimum window substring if the current window is smaller than the previous minimum.\n5. Finally, return the minimum window substring.\n\n### Time Complexity \uD83D\uDE80:\n- The time complexity of this solution is O(m + n), where m is the length of string `s` and n is the length of string `t`. \n- The solution iterates through string `s` once and does constant-time operations within each iteration.\n\n### Space Complexity \uD83D\uDC8E:\n- The space complexity is O(n), where n is the length of string `t`. \n- This is because we use two hash maps of constant size to store the counts of characters in `s` and `t`.\n\n# Code\n```\nclass Solution {\npublic:\n    string minWindow(string s, string t) {\n        ios_base::sync_with_stdio(false);\n        cin.tie(0);\n        cout.tie(0);\n        \n        int len1 = s.length();\n        int len2 = t.length();\n        int start = 0;\n        int ansIndex = -1;\n        int ansLen = INT_MAX;\n        \n        if(len1 < len2) {\n            return "";\n        }\n        \n        unordered_map<char, int> m1;\n        unordered_map<char, int> m2;\n        //to keep track of all characters of P string\n        for(auto x : t) {\n            m2[x]++;\n        }\n        \n        int count = 0;\n        for(int i = 0; i < len1; i++) {\n            char ch = s[i];\n            \n            m1[ch]++;\n            \n            //valid character -> jo character tumhare pattern me bhi ho \n            if(m1[ch] <= m2[ch]) {\n                count++;\n            }\n            \n            if(count == len2) {\n                \n                //window is ready\n                \n                //minimise the window -> freq decrement, ans update , start ko aage badhana h \n                char temp = s[start];\n                while(m1[temp] > m2[temp] or m2[temp] == 0 ) {\n                    \n                    if(m1[temp] > m2[temp])\n                        m1[temp]--;\n                        \n                    start++;\n                    temp = s[start];\n                }\n                \n                //ans update\n                int lengthOfWindow = i - start + 1;\n                if(lengthOfWindow < ansLen ) {\n                    ansLen = lengthOfWindow;\n                    ansIndex = start;\n                }\n                \n                \n            }\n        }\n        \n        if(ansIndex == -1)\n            return "";\n        else\n            return s.substr(ansIndex, ansLen);\n    }\n};\n```\n![lc1.png](https://assets.leetcode.com/users/images/a627dc30-b6dd-47fd-8d95-4809f8f3920f_1707010072.4259968.png)\n
['Hash Table', 'String', 'C', 'Sliding Window', 'Python', 'C++', 'Java', 'JavaScript']