Минимальное окно Python: пустой набор и стоимость срезов

Условие

from collections import Counter

def min_s(a: str, s: str) -> str:
    need = set(a)
    window = Counter()
    res = ""
    c = 0

    left = 0
    best_len = float('inf')

    for right, char in enumerate(s):
        if char in need:
            window[char] += 1
            if window[char] == 1:
                c += 1

        while c == len(need):
            if right - left + 1 < best_len:
                res = s[left:right + 1]
                best_len = right - left + 1

            if s[left] in need:
                window[s[left]] -= 1
                if window[s[left]] == 0:
                    c -= 1

            left += 1

    return res

Ответ

Функция ищет минимальную подстроку, содержащую все различные символы a, но игнорирует их кратность. При пустом a она ошибается, а копирование каждого лучшего среза ухудшает сложность.

Для заявленной set-семантики добавьте проверку пустого a и сохраняйте границы, а срез делайте один раз:

from collections import Counter

def min_s(a, s):
    need = set(a)
    if not need:
        return ''
    counts, covered, left = Counter(), 0, 0
    best = None
    for right, ch in enumerate(s):
        if ch in need:
            counts[ch] += 1
            covered += counts[ch] == 1
        while covered == len(need):
            if best is None or right - left < best[1] - best[0]:
                best = (left, right)
            old = s[left]
            if old in need:
                counts[old] -= 1
                covered -= counts[old] == 0
            left += 1
    return '' if best is None else s[best[0]:best[1] + 1]

Ожидаемое время O(len(a) + len(s)), память O(числа различных символов a), не считая ответа. Если нужны повторения из a, вместо множества нужен Counter требований.