Ctrl K

Записка из газетных заголовков

Средняя
Вы складываете записку message из вырезанных букв. Есть сколько угодно экземпляров газеты с одним и тем же заголовком headline. Из одного экземпляра можно вырезать любые буквы заголовка, но в записку они встают **в том же порядке**, в каком шли в заголовке (то есть каждая копия даёт подпоследовательность headline). Куски из разных копий приклеиваются друг за другом. Верните минимальное число копий, из которых можно сложить message, или -1, если это невозможно.
Пример 1
headline="rain", message="ranin" → 2

Из первой копии вырезаем "ran" (r, a, n), из второй — "in". Двух копий хватает, одной — нет.

Пример 2
headline="news", message="sun" → -1

Буквы u в заголовке нет, сложить записку невозможно.

Пример 3
headline="ab", message="bbb" → 3

Из каждой копии получается только одна буква b — нужно три копии.

Ограничения
  • 1 ≤ len(headline), len(message) ≤ 1000
  • Строки состоят только из строчных латинских букв
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиТройки палочек для треугольника СредняяКуски без общих букв СредняяСамая выгодная подработка для каждого СредняяСамое старшее слияние СредняяОбмены до k-й следующей перестановки Средняя
загружаем Python…
Вход
headline="rain", message="ranin"
Ожидается
2

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 158 тестов на сервере, включая скрытые.