Minimum Window Substring问题

Contact me

• Blog -> https://cugtyt.github.io/blog/index
• Email -> cugtyt@qq.com
• GitHub -> Cugtyt@GitHub

---

题目来源：

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).

Example:

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

Note:

• 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.

这个问题有些麻烦的地方是要找的子串是没有顺序的，而且还不是连续的，所以要找所以可能的位置，所以可能的排列，听起来好复杂的样子，但是网上有个极其精简的解法（来源）：

def minWindow(s, t):
    need, missing = collections.Counter(t), len(t)
    i = I = J = 0
    for j, c in enumerate(s, 1):
        missing -= need[c] > 0
        need[c] -= 1
        if not missing:
            while i < j and need[s[i]] < 0:
                need[s[i]] += 1
                i += 1
            if not J or j - i <= J - I:
                I, J = i, j
    return s[I:J]

由于目标串可能是无序的，不连续的，所以为了检查一个字符串中目标串是否存在，我们采用计数的方法，维护一个Counter，作用就是把每个字符出现的个数存起来，如果一个字符串和目标串的统计数一样，我们认为包含目标串。

一步步看代码逻辑，首先是need和missing，用于存储目标字符串的统计和长度，长度的作用是计算匹配度，如果missing为0，代表完全匹配。然后就是对s的每个字符迭代，目标window从开头开始，遇到一个字符就把统计值减小，直到发现匹配，也就是missing为0，那么就开始对开头进行缩小，缩小的条件是碰到need[s[j]]小于0，这个条件说明字符s[j]不在目标串内，直到不满足，就说明window的起始位置的字符是目标串内的了。如果当前window比原来的小，就更新。

我们必须注意到一些边界情况，比如”bba”和”ba”，如果没有统计个数，那么处理第一个b和第二个b的时候会遇到一些问题。