Search code examples
stringalgorithmpalindrome

Minimum insertion to make a string palindrome

My idea is to find the Length of Longest Palindromic subsequence and subtract it from the string length. Will it work. If no please give an explanation?

Solution

  • find the Length of Longest Palindromic subsequence and subtract it from the string length.

    This will work obviously.

    Another way can be - reverse the original string s into s' and find the LCS (longest common subsequence) of s and s'. The answer is: length(s) - LCS(s, s')