Строки

Можно динамикой попробовать:
Состояние: dp(i) - минимальное количество символов, которое надо удалить, чтобы покрыть префикс строки длины i словами из словаря.
База: dp(0) = 0
Переходы: для i пробовать каждое слово из словаря j - удалять с конца минимум символов, чтобы это слово можно было вставить (жадно идя с конца): dp(i) = min(dp(k) + i - k - word(j).length(), j = 0 .. word.size() - 1)
Что-то такое.
Сложность получится N^2 * M.