[Python 3] From Brute Force to Sliding Window - 3 solutions - O(N)
Solution 1: Brute force\npython\nclass Solution:\n    def minWindow(self, s: str, t: str) -> str:\n        def isCover(cnt1, cnt2): # return True if all charact
**Solution 1: Brute force**\n```python\nclass Solution:\n    def minWindow(self, s: str, t: str) -> str:\n        def isCover(cnt1, cnt2): # return True if all characters in cnt2 is covered by cnt1\n            for k, v in cnt2.items():\n                if cnt1[k] < v:\n                    return False\n            return True\n\n        n = len(s)\n        cntT = Counter(t)\n        ansStartIdx = 0\n        ansSize = math.inf\n        for i in range(n):\n            cnt = Counter()\n            for j in range(i, n):\n                cnt[s[j]] += 1\n                if isCover(cnt, cntT):\n                    if ansSize > j - i + 1:\n                        ansSize = j - i + 1\n                        ansStartIdx = i\n                    break\n\n        if ansSize == math.inf:\n            return ""\n        return s[ansStartIdx:ansStartIdx+ansSize]\n```\n**Complexity**\n- Time: `O(N^2 + M)`, where `N <= 10^5` is length of string `s`, `M <= 10^5` is length of string `t`.\n- Space: `O(1)`\n\n----\n**Solution 2: Sliding Window**\n```python\nclass Solution:\n    def minWindow(self, s: str, t: str) -> str:\n        def isCover(cnt1, cnt2): # return True if all characters in cnt2 is covered by cnt1\n            for k, v in cnt2.items():\n                if cnt1[k] < v:\n                    return False\n            return True\n\n        cntT = Counter(t)\n        cnt = Counter()\n        l = 0\n        ansSize = math.inf\n        ansStartIdx = 0\n        for r, c in enumerate(s):\n            cnt[c] += 1\n            while isCover(cnt, cntT):\n                if ansSize > r - l + 1:\n                    ansSize = r - l + 1\n                    ansStartIdx = l\n                cnt[s[l]] -= 1\n                l += 1\n        if ansSize == math.inf:\n            return ""\n        return s[ansStartIdx : ansStartIdx + ansSize]\n```\n\n**Complexity**\n- Time: `O(26 * N + M)`, where `N <= 10^5` is length of string `s`, `M <= 10^5` is length of string `t`.\n- Space: `O(1)`\n\n----\n**Solution 3: Sliding Window (Optimized)**\n```python\nclass Solution:\n    def minWindow(self, s: str, t: str) -> str:\n        cnt = Counter(t)\n        consumedTarget = len(cnt)\n        consumed = 0\n\n        l = 0\n        ansSize = math.inf\n        ansStartIdx = 0\n        for r, c in enumerate(s):\n            cnt[c] -= 1\n            if cnt[c] == 0:\n                consumed += 1\n\n            while consumed == consumedTarget:  # check if conver all chars of string `t`\n                if ansSize > r - l + 1:\n                    ansSize = r - l + 1\n                    ansStartIdx = l\n                if cnt[s[l]] == 0:\n                    consumed -= 1\n                cnt[s[l]] += 1\n                l += 1\n\n        if ansSize == math.inf:\n            return ""\n        return s[ansStartIdx : ansStartIdx + ansSize]\n```\n\n**Complexity**\n- Time: `O(N + M)`, where `N <= 10^5` is length of string `s`, `M <= 10^5` is length of string `t`.\n- Space: `O(1)`
['Sliding Window']