Техпрогон
ВойтиНачать бесплатно
Код Senior Скользящее окно обновлено

Перестановка как подстрока

Условие

Содержит ли s2 какую-нибудь перестановку s1?

Примеры

checkInclusion("ab", "eidbaooo") // true
checkInclusion("ab", "eidboaoo") // false
checkInclusion("a", "a") // true

Как подойти

Приём со счётчиком missing превращает посимвольное сравнение словарей в O(1) на шаг. Обновлять его надо строго на переходе через точное значение - большее количество символа тоже не годится.

Подсказки: 2
  1. Фиксированное окно длиной s1 плюс счётчик совпавших символов.
  2. Счётчик меняется только когда количество символа становится ровно нужным или перестаёт им быть.

Решите в тренажёре

Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.

Решить в тренажёре

Предыдущий вопрос

Самая длинная серия единиц с k заменами

Следующий вопрос

Самая длинная серия после k замен

Урок по теме

Паттерн: Скользящее окно

Термины по теме

Скользящее окно

Ещё по теме «Скользящее окно»

Все вопросы модуля