Checkpoint Day 4
Yifu Liu
136
Interview

While right is expanding to the end of s, there are two things need to be tracked:

  1. if enough character is in the window
  2. if enough, how we need to remove letter from the left and decrease the satisfied.
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        
        if len(t) > len(s):
            return ''
        
        t_count = collections.Counter(t)
        s_count = collections.defaultdict(int)
        satisfied = left = 0
        length = float('inf')
        res = [0, 0]
        for right in range(len(s)):
            if s[right] in t:
                s_count[s[right]] += 1
                if s_count[s[right]] <= t_count[s[right]]:
                    satisfied += 1 

            while satisfied == len(t):
                if right - left < length:
                    length = right - left
                    res = [left, right]
                if s[left] in t:
                    if t_count[s[left]] == s_count[s[left]]:
                        satisfied -= 1
                    s_count[s[left]] -= 1
                left += 1
        return '' if length == float('inf') else s[res[0]: res[1] + 1]
Comments (1)