Минимальное окно подстроки
Даны две строки s и t. Верните минимальную подстроку строки s, которая содержит все символы строки t, включая дубликаты. Если такой подстроки не существует, верните пустую строку "".
Можно считать, что правильный ответ всегда уникален.
Пример 1:
Input: s = "OUZODYXAZV", t = "XYZ" Output: "YXAZ" Объяснение: "YXAZ" - это кратчайшая подстрока, содержащая символы "X", "Y" и "Z" из строки t.
Рекомендуемая временная и пространственная сложность
Оптимальное решение имеет временную сложность O(n) и пространственную сложность O(k), где n — длина строки s, а k — количество уникальных символов в строке t.
Подсказка 1
Попробуйте использовать технику скользящего окна. Начните с минимального окна и расширяйте его, пока не найдете все необходимые символы.
Подсказка 2
Используйте две хеш-таблицы: одну для подсчета символов в строке t, другую для отслеживания текущего окна.
Подсказка 3
После нахождения валидного окна попробуйте его уменьшить, сдвигая левую границу вправо, пока окно остается валидным.