LC 0076 [H] Minimum Window Substring - ALawliet/algorithms GitHub Wiki

we use (while) because it must be a window that contains all the chars which is more variable than just (if) an at most k thing

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        freq = Counter(t)
        rem = len(t)
        min_win = ''

        l = 0
        for r in range(len(s)):
          cr = s[r]
          if freq[cr] > 0: rem -= 1 # A
          freq[cr] -= 1 # B

          while not rem:
            if not min_win or (r - l + 1) < len(min_win):
              min_win = s[l:r+1]

            cl = s[l] # undo with opposite order for l
            freq[cl] += 1 # B
            if freq[cl] > 0: rem += 1 # A
            l += 1

        return min_win

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        char_to_count = Counter(t)
        len_t_remaining = len(t)
        min_window = ''
        
        l = 0
        for r in range(len(s)):
          # 1. CHOOSE TO APPROACH CONDITION

          # if we see target letter, decrease the total target letter len remaining
          if char_to_count[s[r]] > 0:
            len_t_remaining -= 1 # -Step A

          # decrease letter count for current letter
          # if not target, count just becomes -ve
          char_to_count[s[r]] -= 1 # -Step B

          # if all letters in target are found
          while len_t_remaining == 0: # 2. THE CONDITION HAS BEEN MET
            window_len = r - l + 1
            if not min_window or window_len < len(min_window):
              # found a new smaller window
              min_window = s[l:r+1]

            # 3. UNCHOOSE TO UNDO THE CONDITION

            # count the current letter back
            char_to_count[s[l]] += 1 # +Step B

            # if all target letters have been seen (start of this loop)
            # and now if we see another target letter with count > 0
            # increase target len to be found back, break out of the loop
            if char_to_count[s[l]] > 0:
              len_t_remaining += 1 # +Step A

            l += 1

        return min_window