Контест Senior Скользящее окно обновлено
Минимальное окно, содержащее все символы шаблона
Условие
Даны строки s и t из строчных латинских букв. Найдите самую короткую подстроку s, которая содержит все символы t с учётом кратности (если в t две буквы a, в подстроке их должно быть не меньше двух). Если подходящих подстрок минимальной длины несколько, нужна самая левая.
Ввод: в первой строке s (1 ≤ |s| ≤ 2500), во второй t (1 ≤ |t| ≤ 2500).
Вывод: два числа: длина подстроки и позиция начала (нумерация с 1). Если подстроки нет, выведите 0 0.
Пример 1
Ввод:
adobecodebanc
abc
Вывод:
4 10
Пример 2
Ввод:
a
aa
Вывод:
0 0
Как подойти
Подсказки: 2
- Держите счётчик недостающих символов, а не сравнивайте словари целиком.
- Сдвигайте левый край, пока окно остаётся подходящим.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.
Термины по теме
Ещё по теме «Скользящее окно»
- Самая длинная серия единиц с k заменами
- Перестановка как подстрока
- Самая длинная серия после k замен
- Самая длинная подстрока без повторов
- Максимальная сумма окна длины k
- Максимум гласных в окне
- Кратчайший подмассив с суммой ≥ target
- Самая короткая подстрока с k различными