C++ STL SOLUTION | | 2 APPROACHES | | EASY TO UNDERSTAND
APPROACH 1\n\n## Approach\nSteps:\n1. We first create a hashmap for the characters of the string \'t\'.\n\n\nfor (auto value:t){\n    m[value]++;\n}\n\n\n2. The
# APPROACH 1\n\n## Approach\nSteps:\n1. We first create a hashmap for the characters of the string \'t\'.\n\n```\nfor (auto value:t){\n    m[value]++;\n}\n```\n\n2. Then we use two pointers, left and right to iterate through the string \'s\'. For each index, we do the following-\n\n\n2.1. If s[i] is inside m, the hashmap of t, then we reduce m[s[i]] by 1 and check if its 0; if so, we remove it from the hashmap, because that character requirement has been achieved.\n\n~~~\nif (temp.find(s[right]) != temp.end()){\n\n    // cout<<"found the element\\t"<<temp[s[right]]<<"\\n";\n\n    if (temp[s[right]] == 1){\n        temp.erase(s[right]);\n    }\n    else{\n        temp[s[right]]--;\n    }\n}\n~~~\n\nNote, that these changes are being done to a copy of the hashmap, \'temp\'.\n\n2.2 Similarly, if all elements from the hashmap \'m\' are removed, that means that all the characters have been found in the substring and so we can consider this a valid substring.\n\nIn that case, we calculate the current length = right - left + 1 and compare it with the global minimum and make the necessary changes.\n~~~\nif (temp.size() == 0){\n    // cout<<"temp is empty now\\t";\n    curr_len = right - left + 1;\n    \n    // cout<<"curr_len and min_len is "<<curr_len<<"\\t"<<min_len<<endl;\n    if (curr_len < min_len){\n        min_len = min(min_len,curr_len);\n        res = s.substr(left,curr_len);\n    }\n    temp = m;\n    left++;\n    right = left - 1;\n}\n~~~\n\nNow that we have found the substring, We then reset temp to the original hashmap value, move left by 1 and reset right also.\n\nThe reason why we are doing left++ and not left = right + 1, is because; for example, we can have "ABAODCHJIBC" as s and "ABC" as t.\n\nWe find substring "ABAODC" and then start from left = 0 to find "BAODC" which is a shorter length substring.\n\n\n2.3 If s[i] is not inside the hashmap, then we have two cases, when we are looking to start a substring and when we have already started.\n\nFor example, for "AOBC" with t = "ABC", we have already started the substring at "A" and "O" is not present in the hashmap, so should be ignored. NO CHANGES TO THE LEFT POINTER. When we find the substring "AOBC", left = 0, right = 3, length = right - left + 1 = 4.\n\n\nBut for "OAOBC", we have not started the substring ye, so left should also be moved because it represents the starting point of the substring.\nSo here, left should be incremented from 0 to 1, then when substring "AOBC" is found, left = 1, right = 4, length = 4 - 1 + 1 = 4.\nThe same is implemented here.\n\n~~~\nelse{\n    if (temp == m){\n        left++;\n    }\n    // left++;\n    // cout<<"not found the element so keep going\\n";\n    }\n\n    right++;\n}\n~~~\n\nAfter the whole string has been iterated through, we use substring operator.\n\n## Complexity\n- Time complexity:\nO(n^2)\n\nsince we have to take multiple runs of the string s with size n.\n\n- Space complexity:\nO(m)\n\nwhere m is the size of the string \'t\'. This is because in the worst case where t completely consists of new characters, the hashmap would be of size = n.(worst case being all 26 aphabets present in t).\n\n## Code\n```\nclass Solution {\npublic:\n    string minWindow(string s, string t) {\n        unordered_map<char,int> m;\n\n        if (s.size() < t.size()){\n            return "";\n        }\n\n        for (auto value:t){\n            m[value]++;\n        }\n\n        unordered_map<char,int> temp = m;\n        int left = 0;\n        int right = 0;\n        int min_len = INT_MAX;\n        int curr_len;\n        string res;\n\n        while (right < s.size()){\n            \n            // cout<<"current\\t"<<s[right]<<"\\t";\n\n            //found the element\n            if (temp.find(s[right]) != temp.end()){\n\n                // cout<<"found the element\\t"<<temp[s[right]]<<"\\n";\n\n                if (temp[s[right]] == 1){\n                    temp.erase(s[right]);\n                }\n                else{\n                    temp[s[right]]--;\n                }\n                // cout<<"temp is now of size  "<<temp.size()<<endl;\n                if (temp.size() == 0){\n                    // cout<<"temp is empty now\\t";\n                    curr_len = right - left + 1;\n                    \n                    // cout<<"curr_len and min_len is "<<curr_len<<"\\t"<<min_len<<endl;\n                    if (curr_len < min_len){\n                        min_len = min(min_len,curr_len);\n                        res = s.substr(left,curr_len);\n                    }\n                    temp = m;\n                    right = left;\n                    left++;\n                }\n\n                \n\n            }\n\n            //not found the element\n            else{\n                if (temp == m){\n                    left++;\n                }\n                // left++;\n                // cout<<"not found the element so keep going\\n";\n            }\n\n            right++;\n\n        }\n        \n        return res;\n\n    }\n};\n```\n\n\n# APPROACH 2\n\n## Approach\nSteps:\n1. We first create a hashmap for the characters of the string \'t\'.\n\n```\nfor (auto value:t){\n    m[value]++;\n}\n```\nSame as APPROACH 1.\n\n2. Initialise set<int> unique to store the unique indexes of caught elements. map<char,deque<int>> position to access the initial positions of characters.\n\n\n3. Then for each index, we do the following-\n\n\n3.1. If s[i] is inside m, the hashmap of t, then we add the index to the deque of that character in position. Also add it to the set<int>. We use a set to sort the indexes directly.\n\n3.2 Now, suppose \'t\' has 2 \'A\', but we got 3 \'A\', what we do is check the deque of \'A\', remove that index from the map and the set and then add the latest index, \'i\' in this case.\n\n~~~\nif (m[s[i]] < position[s[i]].size()){\n    int temp = position[s[i]].front();\n    position[s[i]].pop_front();\n    sorted.erase(temp);\n}\n~~~\n\n3.3 If all the required elements are present; which we can do by checking if size of the set is size of t; then we have a valid substring. We then calculate the length and then make changes if current minimum is lesser than the global minimum.\n\n~~~\nif (sorted.size() == t.size()){\n    if (res.second - res.first > i - *sorted.begin()){\n        res = {*sorted.begin(),i};\n        cout<<"res being updated\\t"<<res.first<<"\\t"<<res.second<<endl;\n    }\n}\n~~~\n\nAll credit for the APPROACH 2 solution to - https://leetcode.com/problems/minimum-window-substring/solutions/4673661/easy-o-n-m-sliding-window-detailed-explanation/?envType=daily-question&envId=2024-02-04\n\n## Complexity\n- Time complexity:\nO(n+m)\n\n(where n and m are the sizes of the \'s\' and \'t\' strings)\nSince we have to iterate through s and t once each.\n\n- Space complexity:\nO(m)\n\n\n## Code\n```\nclass Solution {\npublic:\n    string minWindow(string s, string t) {\n        unordered_map<char,int> m;\n\n        if (s.size() < t.size()){\n            return "";\n        }\n\n        for (auto value:t){\n            m[value]++;\n        }\n\n        unordered_map<char,deque<int> > position;\n        set<int> sorted;\n        pair<int,int> res = {0,INT_MAX},initial;\n        initial = {0,INT_MAX};\n        for (int i = 0 ; i < s.size() ; i++){\n            if (m.find(s[i]) != m.end()){\n                \n                position[s[i]].push_back(i);\n                sorted.insert(i);\n\n                //we have too much so remove stuff\n                if (m[s[i]] < position[s[i]].size()){\n                    int temp = position[s[i]].front();\n                    position[s[i]].pop_front();\n                    sorted.erase(temp);\n                }\n\n                if (sorted.size() == t.size()){\n                    if (res.second - res.first > i - *sorted.begin()){\n                        res = {*sorted.begin(),i};\n                        cout<<"res being updated\\t"<<res.first<<"\\t"<<res.second<<endl;\n                    }\n                }\n            }\n        }\n        cout<<res.first<<"\\t"<<res.second<<endl;\n        string ans;\n        if (res != initial){\n            ans = s.substr(res.first,res.second - res.first + 1);\n        }\n\n        else{\n            ans = "";\n        }\n\n        return ans;\n    }\n\n};\n```
['Hash Table', 'String', 'Sliding Window', 'C++']