[Python3] Sliding window O(N+M)
\n# Approach\nThis problem follows the Sliding Window pattern and has a lot of similarities with 567 Permutation in a String with one difference. In this proble
\n# Approach\nThis problem follows the Sliding Window pattern and has a lot of similarities with [567 Permutation in a String](https://leetcode.com/problems/permutation-in-string/description/) with one difference. In this problem, we need to find a substring having all characters of the pattern which means that the required substring can have some additional characters and doesn\u2019t need to be a permutation of the pattern. Here is how we will manage these differences:\n\n1. We will keep a running count of every matching instance of a character.\n2. Whenever we have matched all the characters, we will try to shrink the window from the beginning, keeping track of the smallest substring that has all the matching characters.\n3. We will stop the shrinking process as soon as we remove a matched character from the sliding window. One thing to note here is that we could have redundant matching characters, e.g., we might have two \u2018a\u2019 in the sliding window when we only need one \u2018a\u2019. In that case, when we encounter the first \u2018a\u2019, we will simply shrink the window without decrementing the matched count. We will decrement the matched count when the second \u2018a\u2019 goes out of the window.\n\n# Complexity\n- Time complexity:\nThe time complexity of the above algorithm will be O(N+M) where \u2018N\u2019 and \u2018M\u2019 are the number of characters in the input string and the pattern respectively.\n\n- Space complexity:\nThe space complexity of the algorithm is O(M) since in the worst case, the whole pattern can have distinct characters which will go into the HashMap. In the worst case, we also need O(N) space for the resulting substring, which will happen when the input string is a permutation of the pattern.\n\n# Code\n```python3 []\nclass Solution:\n    def minWindow(self, s: str, t: str) -> str:\n        if len(s) < len(t): return \'\'\n        \n        need, matchCnt, left, resStart, resLen = Counter(t), 0, 0, 0, len(s) + 1\n        \n        for right, ch in enumerate(s):\n            if ch in need:\n                need[ch] -= 1\n                matchCnt += need[ch] == 0\n\n            while matchCnt == len(need):\n                # we found a smaller window, update result\n                curWindowLen = right - left + 1\n                if curWindowLen < resLen:\n                    resStart, resLen = left, curWindowLen\n                \n                removeCh = s[left]\n                left += 1 \n                if removeCh in need:\n                    matchCnt -= need[removeCh] == 0\n                    need[removeCh] += 1\n\n        return s[resStart:resStart + resLen] if resLen <= len(s) else \'\'\n```
['Sliding Window', 'Python', 'Python3']