Ctrl K

Допишите, чтобы слово нашлось

Средняя
Даны строки text и word из строчных латинских букв. В конец text можно дописать сколько угодно букв. Найдите наименьшее число букв, которое нужно дописать, чтобы word стало подпоследовательностью получившейся строки, то есть читалось в ней слева направо, возможно с пропусками других букв между нужными.
Пример 1
text="planet", word="plane" → 0

Буквы p, l, a, n, e уже стоят в text в нужном порядке, дописывать ничего не надо.

Пример 2
text="banana", word="bandana" → 4

Из text удаётся взять только «ban» — после этой n нет d. Дописываем «dana» и получаем «bananadana», где «bandana» читается: b, a, n из начала и d, a, n, a из хвоста.

Пример 3
text="xyz", word="cab" → 3

В text нет буквы c, поэтому дописать придётся слово целиком.

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

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