Sliding Windows||Hash tables->Freq Array||0ms Beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \n2 kinds of solutions. the main idea is the the sliding windows. but for implementation 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n2 kinds of solutions. the main idea is the the sliding windows. but for implementation it needs the info of  frequencies of alphabets.\n1 is just using hash tables (map or unordered_map) which is slow & done many months ago.\nOther is using the frequency arrays to speed up the code; different languages C, C++ & python are used for implementations.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n[Please turn on English subtitles if necessary]\n[https://youtu.be/pi1XpQU_Yxo?si=dsD4W9WVMckv_Rka](https://youtu.be/pi1XpQU_Yxo?si=dsD4W9WVMckv_Rka)\nNote that `s and t consist of uppercase and lowercase English letters`.\nIt is known that \'A\'=65, \'z\'=122. using bitmask with `& 0x3f` to fit in a 64-elemented array.\n\nThe main structure is roughly presented as follows:\n```\n1. Count the frequency table for `t` & store in `tmp`\n2. loop of moving `right` from 0 to end of of `s`:\n    If substring is found which containing `t`:\n        using while-loop compare 2 freq tables moving `left`\n        update min window\n3. return min window if found  otherwise ""\n```\nThe process for finding substrings for testcase `s="ADOBECODEBANC", t="ABC"` which is done by adding some output to the submitted code\n```\n[0,5]:ADOBEC\n[0,9]:ADOBECODEB\n[5,10]:CODEBA\n[9,12]:BANC\n```\n|Method| elapsed time| Time record | Space |\n|---|---|---|---|\n|C++ SW freq arrays|0ms|100%|9.21MB|\n|C++ SW unordered_map|28ms|21.43%|10.43MB|\n|C++ SW map|33ms|16.94%|10.50MB|\n|Python SW freq arrays|65ms|99.48%|17.26MB|\n|C SW freq arrays|2ms|81.82%|6.44MB|\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(|s|+|t|)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(|s|+|t|)$$\n# Codes using freq arrays||C++ 0ms Beats 100%||Python beats 99.48%|| C 2ms\n```C []\n#pragma GCC optimize("O3", "unroll-loops")\nchar* minWindow(char* s, char* t) {\n    int n=strlen(s), tn=0;\n    int left=0;\n    int mp[64]={0}, tmp[64]={0};\n\n    // Count the characters in string t\n    for(char* p=t; *p!=\'\\0\'; p++){\n        int idx=0x3f &(*p);\n    //    printf("%c", *p);\n        tmp[idx]++;\n        tn++;// Count strlen for t\n    }\n    // printf(s);\n\n    int count=0; // Counter for matching characters\n    int minLength=INT_MAX, minLeft = 0; \n\n    for (register right=0; right<n; right++) {\n        int idx = 0x3f & s[right];\n       \n        if (tmp[idx] == 0) continue;\n        mp[idx]++;\n\n        // Check if the current character count matches the required count\n        if (mp[idx] <= tmp[idx]) count++;\n\n        // If all characters of t are found in the current window\n        if (count == tn) {\n            // Try to minimize the window by moving the left pointer\n            int idx_left;// compute idx_left=0x3f&s[left] only once\n            while (tmp[(idx_left= 0x3f & s[left])]==0 || mp[idx_left]>tmp[idx_left]) {\n                if (mp[idx_left]!=0) mp[idx_left]--;\n                left++;\n            }\n\n            // Update the minimum window if necessary\n            if (right-left+1 < minLength) {\n                minLength=right-left+1;\n                minLeft=left;\n            }\n        }\n    }\n\n    // If no valid window found\n    if (minLength == INT_MAX) return "";\n\n    // Return the minimum window substring\n    s[minLeft+minLength] = \'\\0\';\n    return s+minLeft;// substring for C-string\n}\n```\n```python []\nclass Solution:\n    def minWindow(self, s: str, t: str) -> str:\n        n, tn= len(s), len(t)\n        left=0\n        mp=[0]*64\n        tmp=[0]*64\n\n        for c in t:\n            idx=ord(c)& 63\n            tmp[idx]+=1\n    #    print(tmp)\n        count=0\n        minLength=2**31\n        minLeft=0\n\n        for right, c in enumerate(s):\n            idx=ord(c)& 63\n            if tmp[idx]==0: continue\n            mp[idx]+=1\n            if mp[idx]<=tmp[idx]: count+=1\n            if count==tn:\n                while tmp[ll:=(63& ord(s[left]))]==0 or mp[ll]>tmp[ll]:\n                    if mp[ll]!=0: mp[ll]-=1\n                    left+=1\n            #    print("[", left,",", right,"]:",str(s[left:right+1]))\n                if right-left+1<minLength:\n                    minLength=right-left+1\n                    minLeft=left\n        if minLength==2**31: return ""\n        return str(s[minLeft:minLeft+minLength])\n        \n```\n```C++ []\n\nclass Solution {\npublic:\n    string minWindow(string& s, string& t) {//call by reference\n        int n = s.size(), tn= t.size();\n        int left = 0, right;\n        int mp[64]={0}, tmp[64]={0};\n        \n        // Count the characters in string t\n        for (char c : t){\n            int idx=0x3f &c;\n            tmp[idx]++;\n        }\n        \n        int count = 0; // Counter for matching characters\n        \n        int minLength = INT_MAX; // Length of the minimum window\n        int minLeft = 0; // Start index of the minimum window\n        \n        for (right = 0; right < n; right++) {\n            char c = s[right];\n            int idx= 0x3f & c;\n            // Skip characters not present in string t\n            if (tmp[idx] == 0) continue;\n            \n            // Increment the count of matching characters\n            mp[idx]++;\n            \n            // Check if the current character count matches the required count\n            if (mp[idx] <= tmp[idx]) count++;\n            \n            // If all characters of t are found in the current window\n            if (count == tn) {\n                // Try to minimize the window by moving the left pointer\n                while (tmp[0x3f& s[left]]==0|| mp[0x3f& s[left]]>tmp[0x3f& s[left]]) {\n                    if (mp[0x3f&s[left]]!=0) mp[0x3f&s[left]]--;\n                    left++;\n                }\n                \n                // Update the minimum window if necessary\n                if (right - left + 1 < minLength) {\n                    minLength = right - left + 1;\n                    minLeft = left;\n                }\n            }\n        }\n        \n        // If no valid window found, return an empty string\n        if (minLength == INT_MAX) return "";\n        \n        // Return the minimum window substring\n        return s.substr(minLeft, minLength);\n    }\n};\n\n```\n# C++ code with unordered_map done before\n```\nclass Solution {\npublic:\n    string minWindow(string s, string t) {\n        int n = s.size();\n        int tn= t.size();\n        int left = 0, right;\n        unordered_map<char, int> mp, tmp;\n        \n        // Count the characters in string t\n        for (char c : t)\n            tmp[c]++;\n        \n        int count = 0; // Counter for matching characters\n        \n        int minLength = INT_MAX; // Length of the minimum window\n        int minLeft = 0; // Start index of the minimum window\n        \n        for (right = 0; right < n; right++) {\n            char c = s[right];\n            \n            // Skip characters not present in string t\n            if (tmp.count(c) == 0) continue;\n            \n            // Increment the count of matching characters\n            mp[c]++;\n            \n            // Check if the current character count matches the required count\n            if (mp[c] <= tmp[c]) count++;\n            \n            // If all characters of t are found in the current window\n            if (count == tn) {\n                // Try to minimize the window by moving the left pointer\n                while (tmp.count(s[left])==0|| mp[s[left]]>tmp[s[left]]) {\n                    if (mp.count(s[left])!=0) mp[s[left]]--;\n                    left++;\n                }\n                \n                // Update the minimum window if necessary\n                if (right - left + 1 < minLength) {\n                    minLength = right - left + 1;\n                    minLeft = left;\n                }\n            }\n        }\n        \n        // If no valid window found, return an empty string\n        if (minLength == INT_MAX) return "";\n        \n        // Return the minimum window substring\n        return s.substr(minLeft, minLength);\n    }\n};\n```
['Array', 'Hash Table', 'String', 'Bit Manipulation', 'C', 'Sliding Window', 'C++', 'Python3']