text и pattern. Из pattern можно удалить любые символы, чтобы оставшаяся строка стала подпоследовательностью text (то есть получалась из text вычёркиванием символов без перестановки оставшихся).
Стоимость удаления считается так: если ничего не удалено, она равна 0; иначе пусть left — наименьший, а right — наибольший индекс удалённых символов в pattern, и стоимость равна right - left + 1. Обратите внимание: символы между left и right удалять не обязательно, но стоимость от этого не уменьшится — так что выгодно вырезать один сплошной кусок.
Верните минимальную возможную стоимость.text="planet", pattern="plxnt" → 1
Достаточно убрать x (позиция 2): "plnt" встречается в "planet" как подпоследовательность. Стоимость 2 − 2 + 1 = 1.
text="abc", pattern="cba" → 2
Целиком "cba" не подходит, а оставить две буквы в нужном порядке нельзя. Удалив позиции 1 и 2, получаем "c" — стоимость 2.
text="banana", pattern="ana" → 0
"ana" уже подпоследовательность, удалять ничего не нужно.
len(text), len(pattern) ≤ 10⁵text и pattern состоят из строчных латинских буквtext="planet", pattern="plxnt"
1
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 132 теста на сервере, включая скрытые.