Минимальное окно: подсчёт первого появления символа

Условие

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

        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 здесь не учитывается. Сохраняем границы, чтобы не копировать каждый улучшенный результат.

from collections import Counter

def min_s(a: str, s: str) -> str:
    need = set(a)
    if not need:
        return ""
    window = Counter()
    covered = left = 0
    best_start, best_len = 0, len(s) + 1
    for right, char in enumerate(s):
        if char in need:
            window[char] += 1
            if window[char] == 1:
                covered += 1
        while covered == len(need):
            size = right - left + 1
            if size < best_len:
                best_start, best_len = left, size
            outgoing = s[left]
            if outgoing in need:
                window[outgoing] -= 1
                if window[outgoing] == 0:
                    covered -= 1
            left += 1
    return "" if best_len > len(s) else s[best_start:best_start + best_len]

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