LeetCode 76 - Minimum Window Substring - 2022.12.27 solution

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # Maintain a variable of the minimum window substring found so far
        # Maintain a dict count of t
        # Maintain a dict count of s in the current window
        # Maintain a variable 'matches' that tracks how many of the characters in t
        # have all of their necessary matches in s.
        # First create the dict count of t.  Then iterate through s with the first
        # pointer, updating the dict count of s and the 'matches' variable as you go.
        # For each new character, you want to update the dict count of s for that
        # character, then check how it compares to the number of characters needed to
        # match s, and if it matches, increment the 'matches' variable.
        # Once you've hit the needed number of matches, start advancing the left
        # pointer to see how small you can get the string.  Once you hit the point
        # where you no longer have enough matches, then start advancing the right
        # pointer again.
        from collections import defaultdict
        minimum_substring = ''

        # Create the dict count of characters in t
        t_dict = defaultdict(int)
        for char in t:
            t_dict[char] += 1

        remaining_characters_to_match = len(t_dict.keys())

        s_dict = defaultdict(int)

        l = 0
        r = 0
        # we want to keep going as long as the right pointer hasn't hit the end
        # and the current window in s has all the needed characters for t.
        while r < len(s) or remaining_characters_to_match == 0:

            # Increment the right pointer
            while r < len(s) and remaining_characters_to_match > 0:
                current_char_in_s = s[r]
                s_dict[current_char_in_s] += 1 # A: 1

                if s_dict[current_char_in_s] == t_dict[current_char_in_s]:
                    remaining_characters_to_match -= 1

                r += 1

            # Increment the left pointer
            while l <= r and remaining_characters_to_match == 0:

                # Update the min substring if necessary
                if not minimum_substring or (r - l) < len(minimum_substring):
                    minimum_substring = s[l:r+1]

                char_to_remove = s[l]
                s_dict[char_to_remove] -= 1

                if s_dict[char_to_remove] == t_dict[char_to_remove] - 1:
                    remaining_characters_to_match += 1

                l += 1

        return minimum_substring