Minimum number of deletions to make a string palindrome

Given a string of size ‘n’. The task is to remove or delete minimum number of characters from the string so that the resultant string is palindrome.

Note: The order of characters should be maintained.

Examples:

Input : aebcbda
Output : 2
Remove characters 'e' and 'd'
Resultant string will be 'abcba'
which is a palindromic string

Input : techcodebit
Output : 8

simple solution is to remove all subsequences one by one and check if remaining string is palindrome or not. Time complexity of this solution is exponential.

An efficient approach uses the concept of finding the length of the longest palindromic subsequence of a given sequence.

Algorithm:

-->str is the given string.
-->n length of str
-->len be the length of the longest 
   palindromic subsequence of str
-->// minimum number of deletions 
   min = n - len
// C++ implementation to find minimum number
// of deletions to make a string palindromic
#include <bits/stdc++.h>
using namespace std;

// Returns the length of the longest
// palindromic subsequence in 'str'
int lps(string str)
{
    int n = str.size();

    // Create a table to store
    // results of subproblems
    int L[n][n];

    // Strings of length 1
    // are palindrome of length 1
    for (int i = 0; i < n; i++)
        L[i][i] = 1;

    // Build the table. Note that the lower diagonal
    // values of table are useless and not filled in
    // the process. c1 is length of substring
    for (int cl=2; cl<=n; cl++)
    {
        for (int i=0; i<n-cl+1; i++)
        {
            int j = i+cl-1;
            if (str[i] == str[j] && cl == 2)
                L[i][j] = 2;
            else if (str[i] == str[j])
                L[i][j] = L[i+1][j-1] + 2;
            else
                L[i][j] = max(L[i][j-1], L[i+1][j]);
        }
    }

    // length of longest palindromic subseq
    return L[0][n-1];
}

// function to calculate minimum
// number of deletions
int minimumNumberOfDeletions(string str)
{
    int n = str.size();

    // Find longest palindromic subsequence
    int len = lps(str);

    // After removing characters other than
    // the lps, we get palindrome.
    return (n - len);
}

// Driver program to test above
int main()
{
    string str = "techcodebit";
    cout << "Minimum number of deletions = "
         << minimumNumberOfDeletions(str);
    return 0;
}

Output:

Minimum number of deletions = 5

Time Complexity: O(n2)

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/minimum-number-deletions-make-string-palindrome/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

rakesh

Leave a Reply

Your email address will not be published. Required fields are marked *

Skip to toolbar