Минимальное окно: два указателя и непокрытые символы

Условие

# a = "abc", not-empty, unique (m)
# s = "dfaga[bfkac]ebf" => "aceb" (n) O(n)
# s = "cfaafb" => "cfaafb"
# s = "affb" => ""

from collections import Counter

def min_s(a: str, s: str) -> str:
    need = Counter(a)

Ответ

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

Скобки вокруг фрагмента примера считаем разметкой, не символами строки. Для dfagabfkacebf минимальный ответ — aceb, а не отмеченный более длинный участок.

from collections import Counter

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

Ожидаемое время O(m+n), память по числу разных символов. Реализация также учитывает повторения в a, хотя условие гарантирует уникальность.