关于算法:每日一题包含所有字符的最小子串长度

给定字符串 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