[Python] ✅ || Easy Mind Map Diagram || Two Pointer + Sliding Window [Dynamic Size] || Space O(m+n)
Intuition\nThe "Minimum Window Substring" problem requires finding the smallest substring in s that contains all the characters of t. Initially, the challenge s
# Intuition\nThe "Minimum Window Substring" problem requires finding the smallest substring in `s` that contains all the characters of `t`. Initially, the challenge seems to lie in efficiently checking if a substring contains all required characters, and then minimizing this substring. The key is realizing the dynamic nature of the problem, where a \'sliding window\' can expand and contract to encapsulate the required characters.\n\n![dws.png](https://assets.leetcode.com/users/images/d3479479-b8da-4e9e-9b0a-cdfd2b4fc8ef_1704743660.8958838.png)\n\n\n# Approach\nThe approach involves two main phases: window expansion and window contraction. The expansion phase keeps extending the window until it encompasses a valid substring that contains all characters of `t`. Once a valid window is found, the contraction phase begins, shrinking the window from the left while ensuring the window still contains all characters of `t`. The condition `l <= r` in the contraction loop is essential to handle edge cases, particularly when both `s` and `t` are single characters. This rhythm of expanding and contracting continues, always checking for and updating the minimum window found.\n\n# Complexity\n- Time complexity: The time complexity is $$O(m + n)$$, where `m` is the length of `s` and `n` is the length of `t`. This is because each character in `s` is visited at most twice, once by the right pointer and once by the left pointer.\n- Space complexity: The space complexity is $$O(m + n)$$, mainly due to the extra space used for two hash maps (or Counters) for `t` and the current window.\n\n# Code\n```python\nfrom collections import Counter\n\nclass Solution:\n    def minWindow(self, s: str, t: str) -> str:\n        \n        answer_key = Counter(t)\n        window = {}\n        \n        valid_keys_required = len(answer_key)\n        valid_keys_formed = 0\n\n        output = float(\'inf\'), 0, 0 \n        l, r = 0, 0\n\n        # Keep expanding the window until we find a valid substring\n        while r < len(s):\n            char = s[r] \n            window[char] = window.get(char, 0) + 1 \n\n            if char in answer_key and window[char] == answer_key[char]:\n                valid_keys_formed += 1\n\n            while l <= r and valid_keys_formed == valid_keys_required:\n                prev_char = s[l]\n\n                # Make sure to update the value of output before incrementing "l"\n                if output[0] > (r-l+1):\n                    output = (r-l+1), l, r\n                \n                window[prev_char] -= 1\n\n                if prev_char in answer_key and window[prev_char] < answer_key[prev_char]:\n                    valid_keys_formed -= 1\n                \n                l += 1\n            \n            r += 1\n        \n        \n        return "" if output[0] == float(\'inf\') else s[output[1]:output[2]+1]\n```\n
['Hash Table', 'Two Pointers', 'String', 'Sliding Window', 'Python3']