Задача с собеседования в Яндекс

В функцию подается две строки: s и t, где t это непустой алфавит, состоящий из уникальных символов
Надо найти наикратчайшую подстроку в s такую, что она содержит все символы из алфавита t

Наш чат алгоритмистов

Решение должно быть линейно по времени

Решение:
Для удобства заведем хешмапу для быстрой проверки символа в алфавите и поддержания его индекса
Линейно пройдемся правым указателем по строке, поддерживая количество покрытых символов в алфавите, и двигаем левый указатель вправо, пока наша подстрока удовлетворяет условиям

def min_window_with_alphabet(s: str, t: str) -> str:
if not s:
return ""

k = len(t)
mapping = {ch: i for i, ch in enumerate(t)} # char -> index 0..k-1

need = [1] * k
window = [0] * k

required = k
formed = 0

l = 0
best_len = float('inf')
best_l = 0

for r, ch in enumerate(s):
idx = mapping.get(ch)
if idx is not None:
window[idx] += 1
if window[idx] == 1:
formed += 1

while formed == required and l <= r:
cur_len = r - l + 1
if cur_len < best_len:
best_len = cur_len
best_l = l

left_ch = s[l]
idx_l = mapping.get(left_ch)
if idx_l is not None:
window[idx_l] -= 1
if window[idx_l] == 0:
formed -= 1
l += 1

return "" if best_len == float('inf') else s[best_l: best_l + best_len]

@algoses