Longest palindrom by deleting/inserting elements - Algorithms and Problem SolvingAlgorithms and Problem Solving

Longest palindrom by deleting/inserting elements - Algorithms and Problem SolvingAlgorithms and Problem Solving

Given a string. Find minimum number of insertion (or deletions) required to make it a palindrom.

For example, S="abacba" can be transformed into the longest palindrom P1="abacaba" just by inserting 1 char.

Observe that as long as mirror positions has the same character we have a potential palindrome between the mirror positions (inclusive). Note that, mirror of position i in a string of length n, mirror(i) = n-i-1.

We keep searching for characters with a mirror character until we find a character with unequal character at the mirror position. We can either insert a character on the right, or on the left to make the position mirror. we will select the one which will subsequently need less number of inserts to make the rest of the string to palindrome.

For example, S = "abacba"

mirror(S[0]) = S[6-0-1] = S[5] = a, i.e. mirror(S[0]) = S[0], so we can keep looking further in right.
mirror(S[1]) = S[4] = b, i.e. mirror[S[1]] = S[1]. Keep looking further in right.
mirror(S[2]) = S[3] = c, i.e. mirror[S[2]] != S[2]. break!

So, we found a potential substring = S' = S[2..3] = "ac" where we can insert a new character. We can either append a to right or c to left. This will lead S' to be a palindrome "aca" or "cac". Both needs 1 insertions. So, we can select either of this and then keep searching on right until we reach the center of the string. The final solution is that we need 1 character to insert to make S = "abacba" to a palndrom1, P="abacaba" or "abcacba".

Let's derive the recurrence relation. Lets, the minimum number of insertions needed to make the substring from i to j into a palindrome is I[i…j]. str[i…j] can be calculated from smaller subproblems.

I[i..j] = I[i+1..j-1], if S[i] = S[j]  I[i..j] = min{I[i..j-1], I[i+1..j]}+1, otherwise.    Base Case :    I[i,i] = 0, as a single character itself is a palindrome.   

Below is a simple O(n^2) time DP solution to this problem. Note that, we don't actually need to populate upper half of the DP table.

Read full article from Longest palindrom by deleting/inserting elements - Algorithms and Problem SolvingAlgorithms and Problem Solving