solve

problem

This week is just sliding window questions. Not a hard problem to conceptualize: two pointers and a hash table to keep state. However, took me a while to code it out / was stuck on an edge case.

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        target_dict = Counter(t)
        target_sum = sum(target_dict.values())
        curr_sum = 0
        curr_dict = {}
        p1 = 0
        p2 = -1

        curr_min_substring_length = len(s) + 1
        curr_min_substring = s

        while True:

            # we want to move p2 because we haven't hit our target_dict yet
            if curr_sum < target_sum:
                p2 = p2 + 1

                if p2 >= len(s):
                    break

                last_char = s[p2]
                if target_dict.get(last_char):
                    if curr_dict.get(last_char):
                        curr_dict[last_char] = curr_dict[last_char] + 1
                    else:
                        curr_dict[last_char] = 1
                
                    if target_dict[last_char] >= curr_dict[last_char]:
                        curr_sum = curr_sum + 1
            
            # we want to move p1 because we have hit our target
            else: # curr_sum == target_sum

                if p2 - p1 + 1 < curr_min_substring_length:
                    curr_min_substring = s[p1:p2+1]
                    curr_min_substring_length = p2 - p1 + 1

                first_char = s[p1]
                if target_dict.get(first_char):
                    curr_dict[first_char] = curr_dict[first_char] - 1
                    
                    if target_dict[first_char] > curr_dict[first_char]:
                        curr_sum = curr_sum - 1
                
                p1 = p1 + 1
                
                if p1 > p2:
                    p1 = p1 - 1
                    continue

                while target_dict.get(s[p1]) == None:
                    if curr_sum == target_sum:
                        if p2 - p1 + 1 < curr_min_substring_length:
                            curr_min_substring = s[p1:p2+1]
                            curr_min_substring_length = p2 - p1 + 1
                    p1 = p1 + 1

        if curr_min_substring_length == len(s) + 1:
            return ""
        
        return curr_min_substring