【每日一题】包含所有字符的最小子串长度

“

给定字符串 str1 和 str2 ，求 str1 的子串中含有 str2 所有字符的最小子串长度。

【举例】

str1 = “abcde” ，str2 = “ac“ 因为 ”abc“ 包含 str2 所有的字符，并且在满足这一条件的 str1 的所有子串中，”abc“ 是最短的，返回 3.

str1 = “12345” ，str2 = “344“,最小包含子串不存在，返回 0。

”

分析：

使用 left 和 right 维护一个滑动窗口。

• right 移动的时机：窗口没有包含 str2 。扩大窗口。直到窗口内包含了 str2 所有字符。

• left 移动的时机：窗口已经完全有包含 str2 ，此时窗口的长度可能不是最小。在保证窗口内包含str2 所有字符的前提下，减小窗口。直到 map[left] ==0 ，最左端的字符串（str1[right]）的冗余已经删除完毕。

• 综上所述，right 和 left 移动时机，都依赖一个状态：窗口有没有包含 str2，我们可以使用 int match 来维护这个状态。初始值为 match = len(str2)，right 每次移动包括 str2 字符 就需要 match -=1（当 map[str1[right]]<0 时，表示 str1 中多余的字符）。

• 也需要存储一个 map，保存 str2 剩余需要匹配字符的个数。

str1 的长度为 N

str2 的长度为 K

时间复杂度：O(max(N,K))

时间复杂度：O(K)

import sys

def min_len(str1, str2):
    map = dict({(item, 0) for item in str1})

    for item in str2:
        map[item] = map.get(item, 0) + 1
    left = right = 0
    match = len(str2)
    res = sys.maxsize

    while right != len(str1):
        map[str1[right]] -= 1
        if map[str1[right]] >= 0:
            match -= 1
        if match == 0:
            while map[str1[left]] < 0:
                map[str1[left]] += 1
                left += 1
            res = min(res, right - left + 1)
            match += 1
            map[str1[left]] += 1
            left += 1
        right += 1

    return -1 if res == sys.maxsize else res
1