[Python] O(n+m) sliding window, explained
The idea of sliding window with 2 pointers: we create counter cnt_t is frequencies how many time s we need to take each symbol, for example for abca we have a:2
The idea of sliding window with 2 pointers: we create counter `cnt_t` is frequencies how many time s we need to take each symbol, for example for `abca` we have `a:2, b:1, c:1`. We create also `cnt_s` as empty counter, which will keep information about frequencies is current window `[beg, end)` - not that we do not include `end`. To quickly understand how many symbols have good frequency, we have `found` variable. Now, we can have two options to change our window:\n\n1. If `found == len(cnt_t)`, it means that we have in our window all symbols we want: no need to extend it to the right: we will shrink it to the left. We need to update our `ans`, where we keep pair `(end - beg, beg)` , then we look at the first element `old = s[beg]` and if we have `cnt_s[old] == cnt_t[old]` it means that we have exactly the right frequency for this symbol. So, when we move `beg` one position to the right, we need to decrease `found by one. Finally, we decrease frequency by one and more `beg` to the right.\n2.  In the opposite case, first we check if `end == len(s)` and if it is true, we break. Then we look at the new symbol `new = s[end]` (because it was not included, windows are `[beg, end)`. We check if `cnt_s[new] == cnt_t[new] - 1` and if it is the case, it means, that when we add new symbol we need to increase `found` by one. Then we increase frequency and move `end` one position to the right.\n\n#### Complexity\nTime complexity is `O(m + n)`, becuse on each step we move `beg` or `end` one point to the right. Space complexity is `O(A)`, where `A` is the size of alphabet.\n\n#### Code\n```python\nclass Solution:\n    def minWindow(self, s, t):\n        beg, end = 0, 0\n        ans, found = (float("inf"), 0), 0\n        cnt_t, cnt_s = Counter(t), Counter()\n        while end <= len(s):\n            if found == len(cnt_t):\n                ans = min(ans, (end - beg, beg))\n                old = s[beg]\n                if cnt_s[old] == cnt_t[old]: found -= 1\n                cnt_s[old] -= 1\n                beg += 1\n            else:\n                if end == len(s): break\n                new = s[end]\n                if cnt_s[new] == cnt_t[new] - 1: found += 1\n                cnt_s[new] += 1\n                end += 1\n        \n        return s[ans[1]:ans[0]+ans[1]] if ans[0] != float("inf") else ""\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Sliding Window']