Minimum Window Substring

Given a string and a collection of characters, find the shortest substring that contains all the characters. Tags: Sliding Window

Try It!

Discussion

Video

Solution

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        t_counter = collections.Counter(t)
        t_needed = len(t)
        left = 0
        right = 0
        min_len = float('inf')
        min_str = ''

        while right < len(s):
            c_right = s[right]
            if c_right in t_counter:
                count = t_counter[c_right]
                if count > 0:
                    t_needed -= 1
                t_counter[c_right] -= 1

            while t_needed == 0:
                c_left = s[left]
                if c_left in t_counter:
                    count = t_counter[c_left]
                    if count == 0:
                        t_needed += 1
                    t_counter[c_left] += 1

                if right - left + 1 < min_len:
                    min_len = right - left + 1
                    min_str = s[left:right + 1]
                left += 1
            right += 1

        return min_str