5324. Наибольшая общая подпоследовательность
Medium
1 решил
Даны две строки
Нужно, чтобы после вычёркивания обе строки стали одинаковыми. Среди всех таких способов выберите тот, где общая оставшаяся строка самая длинная. Верните эту длину (саму строку возвращать не нужно). Если общих букв с сохранением порядка нет — верните 0.
Буквы в общей строке не обязаны стоять рядом в исходных: важно только, что их порядок тот же.
text1 и text2. Из каждой можно вычеркнуть любые буквы, но оставшиеся нельзя переставлять.Нужно, чтобы после вычёркивания обе строки стали одинаковыми. Среди всех таких способов выберите тот, где общая оставшаяся строка самая длинная. Верните эту длину (саму строку возвращать не нужно). Если общих букв с сохранением порядка нет — верните 0.
Буквы в общей строке не обязаны стоять рядом в исходных: важно только, что их порядок тот же.
text1: a b c d e text2: a c e из первой вычеркнули b и d → осталось ace, как во второй ответ: 3Порядок нельзя ломать:
text1: a b c text2: a c b все три буквы взять нельзя: во второй c стоит раньше b. можно a b или a c → длина 2
Примеры:
Вход:
{"text1": "abcde", "text2": "ace"}
Выход:
3
Объяснение: Из abcde вычёркиваем b и d, остаётся ace — как вторая строка. Буквы a, c, e в первой не стоят рядом, это нормально. Длина → 3.
Вход:
{"text1": "abc", "text2": "abc"}
Выход:
3
Объяснение: Строки уже одинаковые, ничего вычёркивать не нужно → 3.
Вход:
{"text1": "abc", "text2": "def"}
Выход:
0
Объяснение: Ни одной общей буквы, общую строку собрать нельзя → 0.
Ограничения:
1 <= text1.length, text2.length <= 1000
строки состоят из английских букв
Решите эту задачу в браузере
Создайте бесплатный аккаунт — редактор Python, Java, JavaScript и Go, проверка на тестах за секунды.
Комментарии (0)
Зарегистрируйтесь или войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!