Convert string to palindrome string with minimum insertions

Question

In order to find the minimal number of insertions required to convert a given string(s) to palindrome I find the longest common subsequence of the string(lcs_string) and its reverse. Therefore the number of insertions to be made is length(s) - length(lcs_string)

What method should be employed to find the equivalent palindrome string on knowing the number of insertions to be made?

For example :

1) azbzczdzez

Number of insertions required : 5 Palindrome string : azbzcezdzeczbza

Although multiple palindrome strings may exist for the same string but I want to find only one palindrome?

Answer 1

Let S[i, j] represents a sub-string of string S starting from index i and ending at index j (both inclusive) and c[i, j] be the optimal solution for S[i, j].

Obviously, c[i, j] = 0 if i >= j.

In general, we have the recurrence: