Кратчайшая подстрока, покрывающая весь заданный набор символов

Условие

Дан набор символов и строка. Требуется определить в строке подстроку минимальной длины, в которой присутствуют все символы из заданного набора (при этом в подстроке могут встречаться и другие символы).

Ввод: Набор символов: {a, b, c} Текст: "dfagabkaceb" Вывод: "bkac" или "aceb"

Ответ

Используйте скользящее окно: расширяйте правую границу до покрытия набора и сжимайте левую, пока покрытие сохраняется. Для примера подходят окна длины 4: bkac и aceb.

Набор задаёт наличие символов, не их повторную кратность:

def shortest_cover(text, symbols):
    need = set(symbols)
    if not need:
        return ''
    counts = {}
    missing = len(need)
    left = 0
    best = None
    for right, char in enumerate(text):
        if char in need:
            counts[char] = counts.get(char, 0) + 1
            if counts[char] == 1:
                missing -= 1
        while missing == 0:
            if best is None or right - left < best[1] - best[0]:
                best = (left, right)
            old = text[left]
            left += 1
            if old in need:
                counts[old] -= 1
                if counts[old] == 0:
                    missing += 1
    return '' if best is None else text[best[0]:best[1] + 1]

Срез создаётся только в конце. Время O(n), память O(k). При равной длине остаётся первое окно; если покрытия нет, возвращается ''.