Почему это работает
- missing — сколько букв t окну ещё не хватает. Оно меняется, только когда счётчик переходит через 0, поэтому вопрос «покрывает ли окно t?» решается за O(1), без сравнения счётчиков.
- Буква со счётчиком меньше 0 — запасная: если её убрать, missing останется 0. Поэтому окно сужается мимо запасных и ненужных t букв и останавливается, только когда теряет обязательную.
- Для каждого right окно сужается, пока оно ещё покрывает t, поэтому измеряется самое короткое покрывающее окно, которое кончается на right, а best хранит самое короткое из них.
Сложность
Время O(n + m), где n и m — длины s и t: t считается один раз, а каждая буква s один раз входит в окно и не больше одного раза выходит. Память O(k) на счётчики k разных букв.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗