Minimum Window Substring

min_window.py

"""
Description:
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).
- If there is no such window in S that covers all characters in T, return the empty string "".
- If there is such window, you are guaranteed that there will always be only one unique
  minimum window in S.

Examples:
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Input: S = "a", T = "aa"
Output: ""
"""

from collections import defaultdict

def minWindow(s, t):
    """
    :type s: str
    :type t: str
    :rtype: str
    """
    need = defaultdict(int)
    for c in t:
        need[c] += 1
    missing = len(t)
    min_start, min_end = 0, float('inf')
    start = 0
    for end, c in enumerate(s, 1):
        if need[c] > 0:
            missing -= 1
        need[c] -= 1
        if missing == 0:
            while need[s[start]] < 0:
                need[s[start]] += 1
                start += 1
            if end - start < min_end - min_start:
                min_start, min_end = start, end
    return '' if min_end == float('inf') else s[min_start:min_end]