Minimum Window Subsequence

LeetCode 727

"""
find a min substring that contains all unique chars
"""
from collections import Counter

"""
Counter特性
1. 存取時, 若 key 為空時將返回 0 而非 error
2. 蒐集 list 中各項元素還有元素出現的次數

演算法分析:
1. 指標 j, 從字串左往右掃, 一直到滿足子字串為止, 並同時維持各個字母的所需數量(可以負數)
2. 找到後再給另一指標 i, 由左往右掃到 j, 並同時維持各個字母的所需數量 
3. 把 i, j 給 I, J, 為回應當前最短長度
"""
def minWindow(s, p):
    missing = len(p)
    memo = Counter(p)
    I = J = i = j = 0
    
    for j, c in enumerate(s):
        if memo[c] > 0:
            missing = missing - 1
        memo[c] = memo[c] - 1
        
        if missing == 0:
            if J == 0:
                I, J = i, j
            while i <= j and memo[s[i]] < 0:
                memo[s[i]] = memo[s[i]] + 1
                i = i + 1
            if j - i <= J - I:
                I, J = i, j
    return s[I:J+1]

"""
S = "ADOBECODEBANC"
T = "ABC"
"""
s = 'ADOBECODEBANC'
p = set(s)
print("Given String: {}".format(s))
print("pattern: {}".format("".join(p)))
print(minWindow(s,p))