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. Create a vector of size 128, m, to store the count of characters in string t.\n2. Initialize start and end pointers, counter and variables minStart and minLen to store the starting position and length of the minimum window substring.\n3. Traverse the string s from the end pointer and increase the end pointer until you find a valid window:\n4. If the current character in s exists in t, decrease the counter.\n5. Decrease the value of the current character in m.\n6. If a valid window is found, move the start pointer to find a smaller window:\n7. If the current window size is smaller than the minimum length found so far, update the minimum length and start position.\n8. Increase the value of the current character in m.\n9. If the current character exists in t, increase the counter.\n10. Repeat steps 3 and 4 until the end pointer reaches the end of the string s.\n11. If the minimum length is not equal to INT_MAX, return the minimum window substring, otherwise return an empty string.\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++ []\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```Java []\nclass Solution {\n    public String minWindow(String s, String t) {\n        int[] m = new int[128];\n        for (char c : t.toCharArray()) \n            m[c]++;\n        int start = 0, end = 0, counter = t.length(), minStart = 0, minLen = Integer.MAX_VALUE;\n        int size = s.length();\n        while (end < size) {\n            if (m[s.charAt(end++)]-- > 0) \n                counter--;\n            while (counter == 0) {\n                if (end - start < minLen) {\n                    minStart = start;\n                    minLen = end - start;\n                }\n                if (m[s.charAt(start++)]++ == 0) \n                    counter++;\n            }\n        }\n        return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);\n    }\n}\n\n```\n```Python []\nclass Solution:\n    def minWindow(self, s: str, t: str) -> str:\n        m = [0] * 128\n        for c in t:\n            m[ord(c)] += 1\n        start = 0\n        end = 0\n        counter = len(t)\n        minStart = 0\n        minLen = float(\'inf\')\n        size = len(s)\n        while end < size:\n            if m[ord(s[end])] > 0:\n                counter -= 1\n            m[ord(s[end])] -= 1\n            end += 1\n            while counter == 0:\n                if end - start < minLen:\n                    minStart = start\n                    minLen = end - start\n                m[ord(s[start])] += 1\n                if m[ord(s[start])] > 0:\n                    counter\n\n```\n\n# Time Complexity and Space Complexity:\n- Time complexity: **O(n)**, where n is the length of the input string s. This is because the while loop runs at most 2n times in the worst case (when all characters of s are different from t).\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: **O(1)**, as the size of the frequency vector is fixed at 128. This is because the ASCII character set has only 128 characters. The size of other variables used in the algorithm is constant and does not grow with the input size.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->
['Hash Table', 'Sliding Window', 'C++', 'Java', 'Python3']