Подпоследовательности

Эта задача решается с помощью динамического программирования.

Сначала "на пальцах". Пусть у нас строка 2 состоит из 2 символов ab. Тогда a мы в строке 1 должны убирать сначала (сколько нужно) а символы b с конца. При это последний убранный a будет раньше чем первый убранный b (очевидно). Можно уже начинать перебирать границу раздела, поддерживая число символов (за линейно).

Что делать, если строка длиннее. Для простоты понимания с конца. Пусть мы уже взяли предпоследний (N-1) символ строки 2 и он перешёл в j строки 1. Тогда мы должны удалить все последние (N) символы строки 1. Заполнили массив F[N-1][j]. Теперь пусть мы расставили N-2 символов. Используя идею из упрощения с 2 символами мы можем перебрать точку оптимальности (выбрать отрезок [j,k] такой что число элементов равный N на нём плюс F[N-1][k] будет минимально). Так мы получили F[N-2][j]. Повторять N раз.

При правильной реализации сложности будет квадратичная. Если не получается за квадрат - пишите за куб.

P.S. я надеюсь оптимальнее по времени это решать нет необходимости (это возможно).

Возможное решение, но нужно проверять на тестах:

Есть строка "21212122" и подстрока "121"

Для начала посчитаем и запомним позиции вхождения подстроки. У нас есть 2 вхождения на позиции 1 и 3(отсчет от 0). Длинна подстроки 3(121). Для каждого вхождения проверяем цепляем ли мы следующее вхождение.

1(вхождение) + 3(длинна подстроки) -1(отсчет от нуля) = 3
А 3 <= 3(следующие вхождение) Значит удаляем 3 символ. Иначе удаляем любой (допустим 1). И так перебираем все вхождения.

Таким образом мы удалим минимальное количество символов из последовательности

Другой вариант перебором. Находим все вхождения. Идем циклом по вхождениям. Перебором удаляем по 1 символу, затем по 2, итд и проверяем как изменилась строка. В конце перебора удаляем наилучший вариант и идем к следующему вхождению