Simple Python Solution Beats 99% with Detailed Explanation
The key idea is how you update the tracking variables. There are four essentials variables to track: 1. remaing length of a match 2. The position of previous ma
The key idea is how you update the tracking variables. There are four essentials variables to track: 1. remaing length of a match 2. The position of previous matched first element 3. start_position of returned answer 4. end_position of returned answer. \n\nAnd a dictionary to count the occurrence of characters is useful.\n\n```\nclass Solution(object):\n    def minWindow(self, s, t):\n        """\n        :type s: str\n        :type t: str\n        :rtype: str\n        """\n        # Defaultdict is very useful in this problem, though i don\'t like to import modules\n        target_count_dict = collections.defaultdict(int)\n        for ch in t:\n            target_count_dict[ch] += 1\n        remain_missing = len(t)\n        start_pos, end_pos = 0, float(\'inf\')\n        current_start = 0\n        \n        # Enumerate function makes current_end indexes from 1\n        for current_end, ch in enumerate(s, 1):\n            # Whenever we encounter a character, no matter ch in target or not, we minus 1 in count dictionary\n            # But, only when ch is in target, we minus the length of remain_missing\n            # When the remain_missing is 0, we find a potential solution.\n            if target_count_dict[ch] > 0:\n                remain_missing -= 1\n            target_count_dict[ch] -= 1\n            \n            if remain_missing == 0:\n                # Remove redundant character\n                # Try to find the fist position in s that makes target_count_dict value equals 0\n                # Which means we can\'t skip this character in s when returning answer\n                while target_count_dict[s[current_start]] < 0:\n                    target_count_dict[s[current_start]] += 1\n                    current_start += 1\n                if current_end - current_start < end_pos - start_pos:\n                    start_pos, end_pos = current_start, current_end\n                \n                # We need to add 1 to current_start, and the correspondence value in dictionary, is because\n                # this is the first character of the potential answer. So, in future iteration, when we encounter this character,\n                # We can remove this currently first character to try to find a shorter answer.\n                target_count_dict[s[current_start]] += 1\n                remain_missing += 1\n                current_start += 1\n        \n        return s[start_pos:end_pos] if end_pos != float(\'inf\') else ""\n```
[]