Самая длинная общая нить

Средняя

Подпоследовательность строки получается, если вычеркнуть из неё сколько угодно символов (можно ни одного), не меняя порядка оставшихся. Например, "tea" — подпоследовательность строки "theatre", а "eat" — нет. Даны две строки first и second. Найдите длину самой длинной строки, которая является подпоследовательностью обеих. Если общих символов нет, верните 0.

Пример 1

first="bicycle", second="circle" → 4

Одна из самых длинных общих подпоследовательностей — «icle»: в обеих строках буквы i, c, l, e идут именно в таком порядке. Пяти общих букв в нужном порядке не набрать.

Пример 2

first="kayak", second="kayak" → 5

Строки совпадают, общая подпоследовательность — вся строка, длина 5.

Пример 3

first="xyz", second="abc" → 0

Общих букв нет — ответ 0.

Ограничения

1 ≤ first.length, second.length ≤ 1000
Строки состоят только из строчных латинских букв

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

String Dynamic Programming

Вход

first="bicycle", second="circle"

Ожидается

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