# 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 : geeksforgeeks
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:

```-->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++

 `// C++ implementation to find  ` `// minimum number of deletions ` `// to make a string palindromic ` `#include ` `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[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 Code ` `int` `main() ` `{ ` `    ``string str = ``"geeksforgeeks"``; ` `    ``cout << ``"Minimum number of deletions = "` `         ``<< minimumNumberOfDeletions(str); ` `    ``return` `0; ` `} `

## Java

 `// Java implementation to  ` `// find minimum number of  ` `// deletions to make a  ` `// string palindromic ` `class` `GFG ` `{ ` `    ``// Returns the length of ` `    ``// the longest palindromic ` `    ``// subsequence in 'str' ` `    ``static` `int` `lps(String str) ` `    ``{ ` `        ``int` `n = str.length(); ` ` `  `        ``// Create a table to store ` `        ``// results of subproblems ` `        ``int` `L[][] = ``new` `int``[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.charAt(i) ==  ` `                        ``str.charAt(j) && cl == ``2``) ` `                    ``L[i][j] = ``2``; ` `                ``else` `if` `(str.charAt(i) ==  ` `                              ``str.charAt(j)) ` `                    ``L[i][j] = L[i + ``1``][j - ``1``] + ``2``; ` `                ``else` `                    ``L[i][j] = Integer.max(L[i][j - ``1``], ` `                                         ``L[i + ``1``][j]); ` `            ``} ` `        ``} ` ` `  `        ``// length of longest  ` `        ``// palindromic subsequence ` `        ``return` `L[``0``][n - ``1``]; ` `    ``} ` ` `  `    ``// function to calculate minimum ` `    ``// number of deletions ` `    ``static` `int` `minimumNumberOfDeletions(String str) ` `    ``{ ` `        ``int` `n = str.length(); ` ` `  `        ``// Find longest palindromic ` `        ``// subsequence ` `        ``int` `len = lps(str); ` ` `  `        ``// After removing characters ` `        ``// other than the lps, we get ` `        ``// palindrome. ` `        ``return` `(n - len); ` `    ``} ` ` `  `    ``// Driver Code ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``String str = ``"geeksforgeeks"``; ` `        ``System.out.println(``"Minimum number "` `+  ` `                            ``"of deletions = "``+  ` `               ``minimumNumberOfDeletions(str)); ` `    ``} ` `} ` ` `  `// This code is contributed by Sumit Ghosh `

## Python 3

 `# Python 3 implementation to find  ` `# minimum number of deletions ` `# to make a string palindromic ` `  `  `# Returns the length of  ` `# the longest palindromic  ` `# subsequence in 'str' ` `def` `lps(``str``): ` `    ``n ``=` `len``(``str``) ` `  `  `    ``# Create a table to store ` `    ``# results of subproblems ` `    ``L ``=` `[[``0` `for` `x ``in` `range``(n)]``for` `y ``in` `range``(n)] ` `  `  `    ``# Strings of length 1 ` `    ``# are palindrome of length 1 ` `    ``for` `i ``in` `range``(n): ` `        ``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` `cl ``in` `range``( ``2``, n``+``1``): ` `        ``for` `i ``in` `range``(n ``-` `cl ``+` `1``): ` `            ``j ``=` `i ``+` `cl ``-` `1` `            ``if` `(``str``[i] ``=``=` `str``[j] ``and` `cl ``=``=` `2``): ` `                ``L[i][j] ``=` `2` `            ``elif` `(``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 ` `def` `minimumNumberOfDeletions( ``str``): ` ` `  `    ``n ``=` `len``(``str``) ` `  `  `    ``# Find longest palindromic  ` `    ``# subsequence ` `    ``l ``=` `lps(``str``) ` `  `  `    ``# After removing characters  ` `    ``# other than the lps, we  ` `    ``# get palindrome. ` `    ``return` `(n ``-` `l) ` `  `  `# Driver Code ` `if` `__name__ ``=``=` `"__main__"``: ` `     `  `    ``str` `=` `"geeksforgeeks"` `    ``print``( ``"Minimum number of deletions = "` `         ``, minimumNumberOfDeletions(``str``)) `

## C#

 `// C# implementation to find  ` `// minimum number of deletions ` `// to make a string palindromic ` `using` `System; ` ` `  `class` `GFG ` `{ ` `    ``// Returns the length of  ` `    ``// the longest palindromic ` `    ``// subsequence in 'str' ` `    ``static` `int` `lps(String str) ` `    ``{ ` `        ``int` `n = str.Length; ` ` `  `        ``// Create a table to store ` `        ``// results of subproblems ` `        ``int` `[,]L = ``new` `int``[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] = Math.Max(L[i, j - 1],  ` `                                      ``L[i + 1, j]); ` `            ``} ` `        ``} ` ` `  `        ``// length of longest  ` `        ``// palindromic subsequence ` `        ``return` `L[0, n - 1]; ` `    ``} ` ` `  `    ``// function to calculate minimum ` `    ``// number of deletions ` `    ``static` `int` `minimumNumberOfDeletions(``string` `str) ` `    ``{ ` `        ``int` `n = str.Length; ` ` `  `        ``// Find longest palindromic ` `        ``// subsequence ` `        ``int` `len = lps(str); ` ` `  `        ``// After removing characters  ` `        ``// other than the lps, we get ` `        ``// palindrome. ` `        ``return` `(n - len); ` `    ``} ` ` `  `    ``// Driver Code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``string` `str = ``"geeksforgeeks"``; ` `        ``Console.Write(``"Minimum number of"` `+ ` `                          ``" deletions = "` `+  ` `            ``minimumNumberOfDeletions(str)); ` `    ``} ` `} ` ` `  `// This code is contributed by nitin mittal. `

## PHP

 ` `

Output :

```Minimum number of deletions = 8
```

Time Complexity : O(n2)