interview-questions/arrays-and-strings/min_window.py

# Given a string S and a string T,
# find the minimum window in S which will contain all the characters in T in complexity O(n).
# https://leetcode.com/problems/minimum-window-substring/description/
def minWindow(self, s, t):
    # initialize a hash table to store chars and their occurances
    t_table = {i_t: 0 for i_t in t}
    for i_t in t:
        t_table[i_t] += 1
    # two pointers and the window
    begin, end, head = 0, 0, 0
    dist = float('inf')
    len_s = len(s)
    for end in range(len_s):
        # if the char is found in the substring, decrement by 1
        if s[end] in t_table:
            t_table[s[end]] -= 1
        # if all chars are found, start moving the begin pointer
        while all([v <= 0 for v in t_table.values()]):
            if s[begin] in t_table:
                # increment by 1 so that we can check next potential substring
                t_table[s[begin]] += 1
                # store the window if the length is min so far
                if end - begin < dist:
                    head = begin
                    dist = end - head
            begin += 1
    return s[head:(head+dist+1)] if dist < float('inf') else ''