LeetCode 76 - Minimum Window Substring - 2023.10.16 solution

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # This is a dict of t chars to their counts.
        t_counts = get_t_counts(t)

        # A set telling us which chars we need to still get enough of in
        # our subwindow.
        t_chars_we_still_need_to_match = {char for char in t_counts.keys()}

        # This is a list of all the indices that contain characters in t.
        s_window_entries = []

        # This is a dict of the characters in t to their number in the
        # current window in s.
        s_window_counts = defaultdict(int)

        minimum_window_substring = ""

        for i, c in enumerate(s):
            if c not in t_counts:
                continue

            s_window_counts[c] += 1
            s_window_entries.append(i)

            if s_window_counts[c] < t_counts[c]:
                t_chars_we_still_need_to_match.add(c)
            elif s_window_counts[c] >=  t_counts[c] and c in t_chars_we_still_need_to_match:
                t_chars_we_still_need_to_match.remove(c)

            # Check if we should handle a matching subwindow
            if len(t_chars_we_still_need_to_match) == 0:
                # Check if we can remove chars from the front of the
                # subwindow
                while True:
                    if len(s_window_entries) == 0:
                        break
                    front_char_index = s_window_entries[0]
                    front_char = s[front_char_index]
                    if s_window_counts[front_char] > t_counts[front_char]:
                        # Ditch this front char
                        s_window_counts[front_char] -= 1
                        s_window_entries.pop(0)
                    else:
                        break

                # Calculate the subwindow
                current_subwindow_length = s_window_entries[-1] - s_window_entries[0] + 1

                # If the new subwindow is smaller, use it.
                if not minimum_window_substring or current_subwindow_length < len(minimum_window_substring):
                    # Update the minimum window_substring
                    minimum_window_substring = s[s_window_entries[0]:s_window_entries[-1]+1]

                # Pop off the first character in the subwindow so we can start looking for a better subwindow
                front_char = s[s_window_entries[0]]
                s_window_counts[front_char] -= 1
                s_window_entries.pop(0)
                if s_window_counts[front_char] < t_counts[front_char]:
                    t_chars_we_still_need_to_match.add(front_char)
        return minimum_window_substring

def get_t_counts(t):
    t_counts = defaultdict(int)
    for c in t:
        t_counts[c] += 1
    return t_counts