Minimum number of deletions to make a string palindrome | Set 2 | C # program to find minimum deletions to make palindrome . ; Find reverse of input string ; Create a DP table for storing edit distance of string and reverse . ; Find edit distance between input and revInput considering only delete operation . ; Go from bottom left to top right and find the minimum ; Driver Code
using System ; class GFG { static int getLevenstein ( String input ) { String revInput = Reverse ( input ) ; int n = input . Length ; int [ , ] dp = new int [ n + 1 , n + 1 ] ; for ( int i = 0 ; i <= n ; ++ i ) { dp [ 0 , i ] = i ; dp [ i , 0 ] = i ; } for ( int i = 1 ; i <= n ; ++ i ) { for ( int j = 1 ; j <= n ; ++ j ) { if ( input [ i - 1 ] == revInput [ j - 1 ] ) dp [ i , j ] = dp [ i - 1 , j - 1 ] ; else dp [ i , j ] = 1 + Math . Min ( dp [ i - 1 , j ] , dp [ i , j - 1 ] ) ; } } int res = int . MaxValue ; for ( int i = n , j = 0 ; i >= 0 ; i -- , j ++ ) { res = Math . Min ( res , dp [ i , j ] ) ; if ( i < n ) res = Math . Min ( res , dp [ i + 1 , j ] ) ; if ( i > 0 ) res = Math . Min ( res , dp [ i - 1 , j ] ) ; } return res ; } static String Reverse ( String input ) { char [ ] a = input . ToCharArray ( ) ; int l , r = a . Length - 1 ; for ( l = 0 ; l < r ; l ++ , r -- ) { char temp = a [ l ] ; a [ l ] = a [ r ] ; a [ r ] = temp ; } return String . Join ( " " , a ) ; } public static void Main ( String [ ] args ) { String input = " myfirstgeekarticle " ; Console . WriteLine ( getLevenstein ( input ) ) ; } }