Minimum number of deletions to make a string palindrome | C ++ implementation to find minimum number of deletions to make a string palindromic ; Returns the length of the longest palindromic subsequence in ' str ' ; Create a table to store results of subproblems ; Strings of length 1 are palindrome of length 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 ; length of longest palindromic subseq ; function to calculate minimum number of deletions ; Find longest palindromic subsequence ; After removing characters other than the lps , we get palindrome . ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int lps ( string str ) { int n = str . size ( ) ; int L [ n ] [ n ] ; for ( int i = 0 ; i < n ; i ++ ) L [ i ] [ i ] = 1 ; 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 ] ) ; } } return L [ 0 ] [ n - 1 ] ; } int minimumNumberOfDeletions ( string str ) { int n = str . size ( ) ; int len = lps ( str ) ; return ( n - len ) ; } int main ( ) { string str = " geeksforgeeks " ; cout << " Minimum ▁ number ▁ of ▁ deletions ▁ = ▁ " << minimumNumberOfDeletions ( str ) ; return 0 ; }