Longest palindrom by deleting/inserting elements

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.

public static int minInsertionsForLongestPalindrom(final String str) {
    final int n = str.length();
    // L[i][j] contains minimum number of deletes required to make string(i..j) a palindrome
    final int[][] L = new int[n][n];

    // find L for each pair of increasing range (i,j) where i<=j. That is we are only populating upperhalf of the
    // table
    for (int i = 1; i < n; i++) {
        for (int j = i, k = 0; j < n; j++, k++) {
            // if characters are same at the two boundary then no deletions required in these positions.
            // if characters are not same the we can insert either string[i] at the gap between j-1 and j or we
            // can insert string[j] at the gap between i and i+1. We take the min of these
            L[k][j] = str.charAt(k) == str.charAt(j) ? L[k + 1][j - 1] : Math.min(L[k][j - 1], L[k + 1][j]) + 1;
        }
    }

    return L[0][n - 1];
}

Minimum deletes

Let, d[i, j] = Number of deletions required in the str[i,j] to make it palindrome. Let’s derive the recurrence relation for d[i..j] calculated from smaller subproblems.

d[i..j] = d[i+1..j-1], if d[i] = d[j] (i.e. no deletions required)
d[i..j] = min{d[i..j-1], d[i-1..j]}+1, otherwise. (i.e. one deletion required)

Base Case :  
d[i,i] = i 
d[0,j] = j

Minimum inserts and/or deletes 

Minimum insert/delete operations combined
We can solve it by a similar DP approach. If we look closely that we could easily understood that we could solve this problem using DP solution for modified Edit Distance problem (without the replace operation) to transform the original string into its reverse. For example, lets suppose we need to find minimum number of insert/delete necessary to transform the string S=”ababcac” into a palindrome.  The reverse S’=cacbaba. We can transform S into S’ as follows:

"ababcac" > delete(4) => "ababac" > delete(5) => "ababa" > insert(0,c) => "cababa" > insert(2, c) => "cacbaba"

So we need 4 operations to transform S into S’ and hence into a palindrome.

I have another elegant solution. Observe that minimum number of insert/delete operations needed to transform a string into a palindrome is equal to the length of the string minus length of Longest Common Substring (LCS) of the string S and its reverse S’. For example, S = “ababcac” and S’=”cacbaba”. Then LCS(S,S’) = LCS(“ababcac”, “cacbaba”)=”cac”. So, min insert/delete operations needed = length(S)-length(LCA(S,S’))=7-3 = 4.