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.

Minimum inserts

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.

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