Минимальное окно: исправление синтаксиса и двух границ

Условие

# a = "abc", не-пустая, уникальная (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 = set(a)
    window = Counter()
    res = ""
    c = 0

    left = 0
    best_len = float('inf')

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

Ответ

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

from collections import Counter

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

Каждая граница проходит строку один раз: ожидаемое время O(n+m), память O(m). Срез создаётся только после поиска. Примеры из условия дают aceb, cfaafb и пустую строку; квадратные скобки считаются разметкой примера, не частью входа.