# 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

A **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:**

-->stris the given string. -->nlength ofstr-->lenbe the length of the longest palindromic subsequence ofstr-->// minimum number of deletionsmin= n - len

- C++

// 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(n^{2})

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