C++ - Easiest Beginner Friendly Sol || Sliding Window
Intuition of this Problem:\nReference - https://leetcode.com/problems/minimum-window-substring/solutions/26808/here-is-a-10-line-template-that-can-solve-most-su
# Intuition of this Problem:\nReference - https://leetcode.com/problems/minimum-window-substring/solutions/26808/here-is-a-10-line-template-that-can-solve-most-substring-problems/?orderBy=hot\n<!-- Describe your first thoughts on how to solve this problem. -->\n**NOTE - PLEASE READ APPROACH FIRST THEN SEE THE CODE. YOU WILL DEFINITELY UNDERSTAND THE CODE LINE BY LINE AFTER SEEING THE APPROACH.**\n\n# Approach for this Problem:\n1. Initialize a map of size 128 to store the frequency of each character in string t.\n2. Use a counter to keep track of the number of characters in t that have not been found in s yet.\n3. Use two pointers, begin and end, to traverse the string s.\n4. Increment the end pointer until a character is found in t and decrement the frequency of that character in the map. If the frequency of the character in the map becomes zero, decrement the counter.\n5. When the counter reaches zero, it means that all the characters in t have been found in s. Start incrementing the begin pointer until the frequency of the character in the map becomes greater than zero.\n6. Increment the counter when this happens.\n7. Update the minimum window length and starting position if a new minimum window is found.\n8. Repeat steps 3-5 until the end pointer has reached the end of string s.\n9. Return the minimum window substring or an empty string if no such window exists.\n<!-- Describe your approach to solving the problem. -->\n\n# Humble Request:\n- If my solution is helpful to you then please **UPVOTE** my solution, your **UPVOTE** motivates me to post such kind of solution.\n- Please let me know in comments if there is need to do any improvement in my approach, code....anything.\n- **Let\'s connect on** https://www.linkedin.com/in/abhinash-singh-1b851b188\n\n![57jfh9.jpg](https://assets.leetcode.com/users/images/c2826b72-fb1c-464c-9f95-d9e578abcaf3_1674104075.4732099.jpeg)\n\n# Code:\n```C++ []\n//shorter version\nclass Solution {\npublic:\n    string minWindow(string s, string t) {\n        vector<int> map(128,0);\n        for (auto c : t) map[c]++;\n        int counter = t.size(), begin = 0, end = 0, d = INT_MAX, head = 0;\n        while (end < s.size()){\n            if (map[s[end++]]-- > 0) counter--; //in t\n            while (counter == 0){ //valid\n                if (end - begin<d)  d = end - (head = begin);\n                if (map[s[begin++]]++ == 0) counter++;  //make it invalid\n            }  \n        }\n        return d == INT_MAX ? "" : s.substr(head, d);\n    }\n};\n```\n```C++ []\n//detailed version\nclass Solution {\npublic:\n    string minWindow(string s, string t) {\n\t    vector<int> m(128, 0);\n\t    // Statistic for count of char in t\n\t    for (auto c : t) \n            m[c]++;\n\t    // counter represents the number of chars of t to be found in s.\n\t    int start = 0, end = 0, counter = t.size(), minStart = 0, minLen = INT_MAX;\n\t    int size = s.size(); \n\t\n\t    // Move end to find a valid window.\n\t    while (end < size) {\n\t\t    // If char in s exists in t, decrease counter\n\t\t    if (m[s[end]] > 0)\n\t\t\t    counter--;\n\t\t    // Decrease m[s[end]]. If char does not exist in t, m[s[end]] will be negative.\n\t\t    m[s[end]]--;\n\t\t    end++;\n\t\t    // When we found a valid window, move start to find smaller window.\n\t\t    while (counter == 0) {\n\t\t\t    if (end - start < minLen) {\n\t\t\t\t    minStart = start;\n\t\t\t\t    minLen = end - start;\n\t\t\t    }\n\t\t\t    m[s[start]]++;\n\t\t\t    // When char exists in t, increase counter.\n\t\t\t    if (m[s[start]] > 0)\n\t\t\t\t    counter++;\n\t\t\t    start++;\n\t\t    }\n\t    }\n\t    if (minLen != INT_MAX)\n\t\t    return s.substr(minStart, minLen);\n\t    return "";\n    }\n};\n```\n\n# Time Complexity and Space Complexity:\n- Time complexity: **O(|s| + |t|)**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: **O(1)**, as the size of the map is constant and the space required is independent of the size of s and t.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->
['Hash Table', 'String', 'Sliding Window', 'C++']