Minimum Deletions to Make a String Palindrome

Last Updated : 05 May, 2025

Given a string s of length n, the task is to remove or delete the minimum number of characters from the string so that the resultant string is a palindrome.

Note: The order of characters should be maintained.

Examples :

Input : s = "aebcbda"
Output : 2
Explanation: Remove characters 'e' and 'd'. Resultant string will be "abcba" which is a palindromic string
Input: s = "aba"
Output: 0
Explanation: We don't remove any character.

Table of Content

[Naive Approach] Using Recursion - O(2^n) time and O(n) space

The idea is to compare the corner characters first. If the starting index i and ending index j of substring match, then recur for i + 1, j - 1. Otherwise, recur for (i + 1, j) and (i, j - 1) and return the minimum out of these two plus 1.

Recurrence relation will be:

If s[i] equals s[j], we don't need to delete either character, so we recursively check the substring s[i+1...j-1].
If s[i] is not equal to s[j], we have two choices: delete either s[i] or s[j], and take the minimum of these two options.

This can be expressed as:

minDel(i, j) = 0, if i >= j (base case)
minDel(i, j) = minDel(i+1, j-1), if s[i] == s[j]
minDel(i, j) = 1 + min(minDel(i+1, j), minDel(i, j-1)), if s[i] != s[j]

C++

// C++ program to find Minimum number of  // deletions to make a string palindrome #include <iostream> using namespace std; // Function to calculate the minimum number of  // deletions to make substring s[i..j] palindrome. int minDelRecur(int i, int j, string &s) {    // Base Case:  if (i >= j) return 0;    // If s[i] is equal to s[j]  if (s[i] == s[j]) {  return minDelRecur(i+1, j-1, s);  }    // Else we have to delete either of  // s[i] or s[j].  return 1 + min(minDelRecur(i+1, j, s), minDelRecur(i, j-1, s)); } // Function to calculate the minimum // Element required to delete for // Making string palindrome int minDeletions(string &s) {  int n = s.length();  return minDelRecur(0, n-1, s); } int main() {  string s = "aebcbda";  cout << minDeletions(s);  return 0; }

Java

// Java program to find Minimum number of  // deletions to make a string palindrome class GfG {  // Function to calculate the minimum number of   // deletions to make substring s[i..j] palindrome.  static int minDelRecur(int i, int j, String s) {  // Base Case:  if (i >= j) return 0;  // If s[i] is equal to s[j]  if (s.charAt(i) == s.charAt(j)) {  return minDelRecur(i + 1, j - 1, s);  }  // Else we have to delete either of  // s[i] or s[j].  return 1 + Math.min(minDelRecur(i + 1, j, s), minDelRecur(i, j - 1, s));  }  // Function to calculate the minimum  // Element required to delete for  // Making string palindrome  static int minDeletions(String s) {  int n = s.length();  return minDelRecur(0, n - 1, s);  }  public static void main(String[] args) {  String s = "aebcbda";  System.out.println(minDeletions(s));  } }

Python

# Python program to find Minimum number of  # deletions to make a string palindrome # Function to calculate the minimum number of  # deletions to make substring s[i..j] palindrome. def minDelRecur(i, j, s): # Base Case: if i >= j: return 0 # If s[i] is equal to s[j] if s[i] == s[j]: return minDelRecur(i + 1, j - 1, s) # Else we have to delete either of # s[i] or s[j]. return 1 + min(minDelRecur(i + 1, j, s), minDelRecur(i, j - 1, s)) # Function to calculate the minimum # Element required to delete for # Making string palindrome def minDeletions(s): n = len(s) return minDelRecur(0, n - 1, s) if __name__ == "__main__": s = "aebcbda" print(minDeletions(s))

// C# program to find Minimum number of  // deletions to make a string palindrome using System; class GfG {  // Function to calculate the minimum number of   // deletions to make substring s[i..j] palindrome.  static int minDelRecur(int i, int j, string s) {  // Base Case:  if (i >= j) return 0;  // If s[i] is equal to s[j]  if (s[i] == s[j]) {  return minDelRecur(i + 1, j - 1, s);  }  // Else we have to delete either of  // s[i] or s[j].  return 1 + Math.Min(minDelRecur(i + 1, j, s), minDelRecur(i, j - 1, s));  }  // Function to calculate the minimum  // Element required to delete for  // Making string palindrome  static int minDeletions(string s) {  int n = s.Length;  return minDelRecur(0, n - 1, s);  }  static void Main(string[] args) {  string s = "aebcbda";  Console.WriteLine(minDeletions(s));  } }

JavaScript

// JavaScript program to find Minimum number of  // deletions to make a string palindrome // Function to calculate the minimum number of  // deletions to make substring s[i..j] palindrome. function minDelRecur(i, j, s) {  // Base Case:  if (i >= j) return 0;  // If s[i] is equal to s[j]  if (s[i] === s[j]) {  return minDelRecur(i + 1, j - 1, s);  }  // Else we have to delete either of  // s[i] or s[j].  return 1 + Math.min(minDelRecur(i + 1, j, s), minDelRecur(i, j - 1, s)); } // Function to calculate the minimum // Element required to delete for // Making string palindrome function minDeletions(s) {  let n = s.length;  return minDelRecur(0, n - 1, s); } let s = "aebcbda"; console.log(minDeletions(s));

Output

[Better Approach - 1] Using Top-Down DP (Memoization) – O(n^2) time and O(n^2) space

1. Optimal Substructure: The minimum number of deletions required to make substring s[i...j] a palindrome, i.e., minDel(i, j, s, memo), depends on the optimal solutions of the subproblems. There are two cases:
If s[i] == s[j], then minDel(i, j, s, memo) = minDel(i+1, j-1, s, memo) (we don't need to delete either character)
If s[i] != s[j], then minDel(i, j, s, memo) = 1 + min(minDel(i+1, j, s, memo), minDel(i, j-1, s, memo)) (we delete either the first or last character, whichever gives the minimum result)
2. Overlapping Subproblems: While applying a recursive approach to this problem, we notice that certain substring calculations are computed multiple times, especially for longer strings.

Follow the below steps to implement the idea:

Since there are two parameters that change during recursive calls (i and j), we create a 2D memo array to store the results of previously solved subproblems.
memo[i][j] will represent the minimum number of deletions required to make the substring s[i...j] a palindrome.
We initialize the memo array with -1 to indicate that no computation has been done for that subproblem yet.

C++

// C++ program to find Minimum number of  // deletions to make a string palindrome  #include <iostream> #include <vector> using namespace std; // Function to calculate the minimum number of  // deletions to make substring s[i..j] palindrome. int minDelRecur(int i, int j, string &s, vector<vector<int>> &memo) {    // Base Case:  if (i >= j) return 0;    // If already calculated  if (memo[i][j] != -1) return memo[i][j];    // If s[i] is equal to s[j]  if (s[i] == s[j]) {  memo[i][j] = minDelRecur(i+1, j-1, s, memo);  } else {    // Else we have to delete either of s[i] or s[j]  memo[i][j] = 1 + min(minDelRecur(i+1, j, s, memo),   minDelRecur(i, j-1, s, memo));  }    return memo[i][j]; } // Function to calculate the minimum // Element required to delete for // Making string palindrome int minDeletions(string &s) {  int n = s.length();  vector<vector<int>> memo(n, vector<int>(n, -1));  return minDelRecur(0, n-1, s, memo); } int main() {  string s = "aebcbda";  cout << minDeletions(s);  return 0; }

Java

// Java program to find Minimum number of  // deletions to make a string palindrome  class GfG {  // Function to calculate the minimum number of   // deletions to make substring s[i..j] palindrome.  static int minDelRecur(int i, int j, String s, int[][] memo) {    // Base Case:  if (i >= j) return 0;    // If already calculated  if (memo[i][j] != -1) return memo[i][j];    // If s[i] is equal to s[j]  if (s.charAt(i) == s.charAt(j)) {  memo[i][j] = minDelRecur(i + 1, j - 1, s, memo);  } else {    // Else we have to delete either of s[i] or s[j]  memo[i][j] = 1 + Math.min(minDelRecur(i + 1, j, s, memo),  minDelRecur(i, j - 1, s, memo));  }  return memo[i][j];  }  // Function to calculate the minimum  // Element required to delete for  // Making string palindrome  static int minDeletions(String s) {  int n = s.length();  int[][] memo = new int[n][n];  for (int i = 0; i < n; i++) {  for (int j = 0; j < n; j++) {  memo[i][j] = -1;  }  }  return minDelRecur(0, n - 1, s, memo);  }  public static void main(String[] args) {  String s = "aebcbda";  System.out.println(minDeletions(s));  } }

Python

# Python program to find Minimum number of  # deletions to make a string palindrome  # Function to calculate the minimum number of  # deletions to make substring s[i..j] palindrome. def minDelRecur(i, j, s, memo): # Base Case: if i >= j: return 0 # If already calculated if memo[i][j] != -1: return memo[i][j] # If s[i] is equal to s[j] if s[i] == s[j]: memo[i][j] = minDelRecur(i + 1, j - 1, s, memo) else: # Else we have to delete either of s[i] or s[j] memo[i][j] = 1 + min(minDelRecur(i + 1, j, s, memo), minDelRecur(i, j - 1, s, memo)) return memo[i][j] # Function to calculate the minimum # Element required to delete for # Making string palindrome def minDeletions(s): n = len(s) memo = [[-1 for _ in range(n)] for _ in range(n)] return minDelRecur(0, n - 1, s, memo) if __name__ == "__main__": s = "aebcbda" print(minDeletions(s))

// C# program to find Minimum number of  // deletions to make a string palindrome  using System; class GfG {  // Function to calculate the minimum number of   // deletions to make substring s[i..j] palindrome.  static int minDelRecur(int i, int j, string s, int[,] memo) {    // Base Case:  if (i >= j) return 0;  // If already calculated  if (memo[i,j] != -1) return memo[i,j];  // If s[i] is equal to s[j]  if (s[i] == s[j]) {  memo[i,j] = minDelRecur(i + 1, j - 1, s, memo);  } else {    // Else we have to delete either of s[i] or s[j]  memo[i,j] = 1 + Math.Min(minDelRecur(i + 1, j, s, memo),  minDelRecur(i, j - 1, s, memo));  }  return memo[i,j];  }  // Function to calculate the minimum  // Element required to delete for  // Making string palindrome  static int minDeletions(string s) {  int n = s.Length;  int[,] memo = new int[n, n];  for (int i = 0; i < n; i++) {  for (int j = 0; j < n; j++) {  memo[i, j] = -1;  }  }  return minDelRecur(0, n - 1, s, memo);  }  static void Main(string[] args) {  string s = "aebcbda";  Console.WriteLine(minDeletions(s));  } }

JavaScript

// JavaScript program to find Minimum number of  // deletions to make a string palindrome  // Function to calculate the minimum number of  // deletions to make substring s[i..j] palindrome. function minDelRecur(i, j, s, memo) {    // Base Case:  if (i >= j) return 0;  // If already calculated  if (memo[i][j] !== -1) return memo[i][j];  // If s[i] is equal to s[j]  if (s[i] === s[j]) {  memo[i][j] = minDelRecur(i + 1, j - 1, s, memo);  } else {    // Else we have to delete either of s[i] or s[j]  memo[i][j] = 1 + Math.min(minDelRecur(i + 1, j, s, memo),  minDelRecur(i, j - 1, s, memo));  }  return memo[i][j]; } // Function to calculate the minimum // Element required to delete for // Making string palindrome function minDeletions(s) {  const n = s.length;  const memo = Array.from({ length: n }, () => Array(n).fill(-1));  return minDelRecur(0, n - 1, s, memo); } const s = "aebcbda"; console.log(minDeletions(s));

Output

[Better Approach - 2] Using Bottom-Up DP (Tabulation) – O(n^2) time and O(n^2) space

The idea is to fill the DP table based on previously computed values. For each position pair (i,j) in the string, we determine the minimum number of deletions needed to make the substring s[i...j] a palindrome. The table is filled in an iterative manner by first handling smaller substrings and gradually building up to the entire string.

The dynamic programming relation is as follows:

If s[i] == s[j], then dp[i][j] = dp[i+1][j-1] (no deletion needed for matching characters)
If s[i] != s[j], then dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1]) (delete either the first or last character, whichever gives the minimum result)

C++

// C++ program to find Minimum number of  // deletions to make a string palindrome  #include <iostream> #include <vector> using namespace std; // Function to calculate the minimum // Element required to delete for // Making string palindrome int minDeletions(string &s) {  int n = s.length();  vector<vector<int>> dp(n, vector<int>(n, 0));    // Fill the dp table  // l is the length of substring  for (int l = 2; l <= n; l++) {  for (int i = 0; i <= n - l; i++) {  int j = i + l - 1;    // If there are only 2 characters  if (l == 2) {  dp[i][j] = (s[i] == s[j]) ? 0 : 1;  }   else {    // If first and last characters match  if (s[i] == s[j]) {  dp[i][j] = dp[i+1][j-1];  }   else {    // If they don't match, consider minimum of two choices  dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1]);  }  }  }  }    // Return minimum deletions for entire string  return dp[0][n-1]; } int main() {  string s = "aebcbda";  cout << minDeletions(s);  return 0; }

Java

// Java program to find Minimum number of  // deletions to make a string palindrome  class GfG {  // Function to calculate the minimum  // Element required to delete for  // Making string palindrome  static int minDeletions(String s) {  int n = s.length();  int[][] dp = new int[n][n];  // Fill the dp table  // l is the length of substring  for (int l = 2; l <= n; l++) {  for (int i = 0; i <= n - l; i++) {  int j = i + l - 1;  // If there are only 2 characters  if (l == 2) {  dp[i][j] = (s.charAt(i) == s.charAt(j)) ? 0 : 1;  }   else {  // If first and last characters match  if (s.charAt(i) == s.charAt(j)) {  dp[i][j] = dp[i+1][j-1];  }   else {  // If they don't match, consider minimum of two choices  dp[i][j] = 1 + Math.min(dp[i+1][j], dp[i][j-1]);  }  }  }  }  // Return minimum deletions for entire string  return dp[0][n-1];  }  public static void main(String[] args) {  String s = "aebcbda";  System.out.println(minDeletions(s));  } }

Python

# Python program to find Minimum number of  # deletions to make a string palindrome  # Function to calculate the minimum # Element required to delete for # Making string palindrome def minDeletions(s): n = len(s) dp = [[0]*n for _ in range(n)] # Fill the dp table # l is the length of substring for l in range(2, n+1): for i in range(n - l + 1): j = i + l - 1 # If there are only 2 characters if l == 2: dp[i][j] = 0 if s[i] == s[j] else 1 else: # If first and last characters match if s[i] == s[j]: dp[i][j] = dp[i+1][j-1] else: # If they don't match, consider minimum of two choices dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1]) # Return minimum deletions for entire string return dp[0][n-1] if __name__ == "__main__": s = "aebcbda" print(minDeletions(s))

// C# program to find Minimum number of  // deletions to make a string palindrome  using System; class GfG {  // Function to calculate the minimum  // Element required to delete for  // Making string palindrome  static int minDeletions(string s) {  int n = s.Length;  int[,] dp = new int[n, n];  // Fill the dp table  // l is the length of substring  for (int l = 2; l <= n; l++) {  for (int i = 0; i <= n - l; i++) {  int j = i + l - 1;  // If there are only 2 characters  if (l == 2) {  dp[i,j] = (s[i] == s[j]) ? 0 : 1;  }   else {  // If first and last characters match  if (s[i] == s[j]) {  dp[i,j] = dp[i+1,j-1];  }   else {  // If they don't match, consider minimum of two choices  dp[i,j] = 1 + Math.Min(dp[i+1,j], dp[i,j-1]);  }  }  }  }  // Return minimum deletions for entire string  return dp[0,n-1];  }  static void Main(string[] args) {  string s = "aebcbda";  Console.WriteLine(minDeletions(s));  } }

JavaScript

// JavaScript program to find Minimum number of  // deletions to make a string palindrome  // Function to calculate the minimum // Element required to delete for // Making string palindrome function minDeletions(s) {  let n = s.length;  let dp = new Array(n).fill(0).map(() => new Array(n).fill(0));  // Fill the dp table  // l is the length of substring  for (let l = 2; l <= n; l++) {  for (let i = 0; i <= n - l; i++) {  let j = i + l - 1;  // If there are only 2 characters  if (l === 2) {  dp[i][j] = (s[i] === s[j]) ? 0 : 1;  }   else {  // If first and last characters match  if (s[i] === s[j]) {  dp[i][j] = dp[i+1][j-1];  }   else {  // If they don't match, consider minimum of two choices  dp[i][j] = 1 + Math.min(dp[i+1][j], dp[i][j-1]);  }  }  }  }  // Return minimum deletions for entire string  return dp[0][n-1]; } let s = "aebcbda"; console.log(minDeletions(s));

Output

[Efficient Approach - 1] Using Space Optimized DP - O(n^2) time and O(n) space

In the previous approach of dynamic programming, we derived the relation between states as given below:
If s[i] == s[j], then dp[i][j] = dp[i+1][j-1] (characters match, no deletion needed)
else dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1]) (characters don't match, delete one)
If we observe the recurrence relation carefully, for calculating the current dp[i][j] state, we need:
The value from two rows back at position dp[i+1][j-1] (when characters match)
Values from the previous row at position dp[i+1][j] and current row at position dp[i][j-1] (when characters don't match)
Due to this dependency pattern, we need to maintain three arrays instead of the full 2D matrix:
prev2: stores the values from two rows back (l-2)
prev1: stores the values from the previous row (l-1)
curr: stores the values for the current row (l)

C++

// C++ program to find Minimum number of  // deletions to make a string palindrome  #include <iostream> #include <vector> using namespace std; // Function to calculate the minimum // Element required to delete for // Making string palindrome int minDeletions(string &s) {  int n = s.length();    // We need 3 arrays: current and two previous rows  vector<int> prev1(n, 0), curr(n, 0), prev2(n, 0);    // Fill the dp table  // l is the length of substring  for (int l = 2; l <= n; l++) {    // Update current row   for (int i = n-l; i >= 0; i--) {  int j = i + l - 1;    // If there are only 2 characters  if (l == 2) {  curr[i] = (s[i] == s[j]) ? 0 : 1;  }   else {    // If first and last characters match  if (s[i] == s[j]) {  curr[i] = prev2[i+1];  }   else {  // If they don't match, consider minimum of two choices  curr[i] = 1 + min(prev1[i], prev1[i+1]);  }  }  }  // Update previous with current for next iteration  prev2 = prev1;  prev1 = curr;  }    // Return minimum deletions for entire string  return prev1[0]; } int main() {  string s = "aebcbda";  cout << minDeletions(s);  return 0; }

Java

// Java program to find Minimum number of  // deletions to make a string palindrome  class GfG {  // Function to calculate the minimum  // Element required to delete for  // Making string palindrome  static int minDeletions(String s) {  int n = s.length();  // We need 3 arrays: current and two previous rows  int[] prev1 = new int[n];  int[] curr = new int[n];  int[] prev2 = new int[n];  // Fill the dp table  // l is the length of substring  for (int l = 2; l <= n; l++) {  // Update current row   for (int i = n - l; i >= 0; i--) {  int j = i + l - 1;  // If there are only 2 characters  if (l == 2) {  curr[i] = (s.charAt(i) == s.charAt(j)) ? 0 : 1;  }   else {  // If first and last characters match  if (s.charAt(i) == s.charAt(j)) {  curr[i] = prev2[i + 1];  }   else {  // If they don't match, consider minimum of two choices  curr[i] = 1 + Math.min(prev1[i], prev1[i + 1]);  }  }  }  // Update previous with current for next iteration  prev2 = prev1.clone();  prev1 = curr.clone();  }  // Return minimum deletions for entire string  return prev1[0];  }  public static void main(String[] args) {  String s = "aebcbda";  System.out.println(minDeletions(s));  } }

Python

# Python program to find Minimum number of  # deletions to make a string palindrome  # Function to calculate the minimum # Element required to delete for # Making string palindrome def minDeletions(s): n = len(s) # We need 3 arrays: current and two previous rows prev1 = [0] * n curr = [0] * n prev2 = [0] * n # Fill the dp table # l is the length of substring for l in range(2, n + 1): # Update current row  for i in range(n - l, -1, -1): j = i + l - 1 # If there are only 2 characters if l == 2: curr[i] = 0 if s[i] == s[j] else 1 else: # If first and last characters match if s[i] == s[j]: curr[i] = prev2[i + 1] else: # If they don't match, consider minimum of two choices curr[i] = 1 + min(prev1[i], prev1[i + 1]) # Update previous with current for next iteration prev2 = prev1[:] prev1 = curr[:] # Return minimum deletions for entire string return prev1[0] if __name__ == "__main__": s = "aebcbda" print(minDeletions(s))

// C# program to find Minimum number of  // deletions to make a string palindrome with space optimization using System; class GfG {  // Function to calculate the minimum  // Element required to delete for  // Making string palindrome  static int minDeletions(string s) {  int n = s.Length;  // We need 3 arrays: current and two previous rows  int[] prev1 = new int[n];  int[] curr = new int[n];  int[] prev2 = new int[n];  // Fill the dp table  // l is the length of substring  for (int l = 2; l <= n; l++) {  // Update current row   for (int i = n - l; i >= 0; i--) {  int j = i + l - 1;  // If there are only 2 characters  if (l == 2) {  curr[i] = (s[i] == s[j]) ? 0 : 1;  }   else {  // If first and last characters match  if (s[i] == s[j]) {  curr[i] = prev2[i + 1];  }   else {  // If they don't match, consider minimum of two choices  curr[i] = 1 + Math.Min(prev1[i], prev1[i + 1]);  }  }  }  // Update previous with current for next iteration  prev2 = (int[])prev1.Clone();  prev1 = (int[])curr.Clone();  }  // Return minimum deletions for entire string  return prev1[0];  }  static void Main(string[] args) {  string s = "aebcbda";  Console.WriteLine(minDeletions(s));  } }

JavaScript

// JavaScript program to find Minimum number of  // deletions to make a string palindrome with space optimization // Function to calculate the minimum // Element required to delete for // Making string palindrome function minDeletions(s) {  let n = s.length;  // We need 3 arrays: current and two previous rows  let prev1 = new Array(n).fill(0);  let curr = new Array(n).fill(0);  let prev2 = new Array(n).fill(0);  // Fill the dp table  // l is the length of substring  for (let l = 2; l <= n; l++) {  // Update current row   for (let i = n - l; i >= 0; i--) {  let j = i + l - 1;  // If there are only 2 characters  if (l === 2) {  curr[i] = (s[i] === s[j]) ? 0 : 1;  }   else {  // If first and last characters match  if (s[i] === s[j]) {  curr[i] = prev2[i + 1];  }   else {  // If they don't match, consider minimum of two choices  curr[i] = 1 + Math.min(prev1[i], prev1[i + 1]);  }  }  }  // Update previous with current for next iteration  prev2 = [...prev1];  prev1 = [...curr];  }  // Return minimum deletions for entire string  return prev1[0]; } let s = "aebcbda"; console.log(minDeletions(s));

Output

[Expected Approach - 2] Using Length of Longest Palindromic Subsequence - O(n^2) time and O(n) space

The idea is to find the length of the longest palindromic subsequence, and then subtracting this length from the total length of string will give the minimum number of deletions to make the string palindrome.

C++

// C++ program to find Minimum number of  // deletions to make a string palindrome #include <iostream> #include <vector> using namespace std; // Function to find the length of the lps int longestPalinSubseq(string &s) {  int n = s.size();  // Create two vectors: one for the current state (dp)  // and one for the previous state (dpPrev)  vector<int> curr(n), prev(n);  // Loop through the string in reverse (starting from the end)  for (int i = n - 1; i >= 0; --i){  // Initialize the current state of dp  curr[i] = 1;  // Loop through the characters ahead of i  for (int j = i + 1; j < n; ++j){  // If the characters at i and j are the same  if (s[i] == s[j]){  // Add 2 to the length of the palindrome between them  curr[j] = prev[j - 1] + 2;  }  else{  // Take the maximum between excluding either i or j  curr[j] = max(prev[j], curr[j - 1]);  }  }  // Update previous to the current state of dp  prev = curr;  }  return curr[n-1]; } // Function to calculate the minimum // Element required to delete for // Making string palindrome int minDeletions(string &s) {  int n = s.length();    // Find the LPS   int lps = longestPalinSubseq(s);    return n - lps; } int main() {  string s = "aebcbda";  cout << minDeletions(s);  return 0; }

Java

// Java program to find Minimum number of  // deletions to make a string palindrome import java.util.*; class GfG {  // Function to find the length of the lps  static int longestPalinSubseq(String s) {  int n = s.length();  // Create two vectors: one for the current state (dp)  // and one for the previous state (dpPrev)  int[] curr = new int[n];  int[] prev = new int[n];  // Loop through the string in reverse (starting from the end)  for (int i = n - 1; i >= 0; --i) {  // Initialize the current state of dp  curr[i] = 1;  // Loop through the characters ahead of i  for (int j = i + 1; j < n; ++j) {  // If the characters at i and j are the same  if (s.charAt(i) == s.charAt(j)) {  // Add 2 to the length of the palindrome between them  curr[j] = prev[j - 1] + 2;  } else {  // Take the maximum between excluding either i or j  curr[j] = Math.max(prev[j], curr[j - 1]);  }  }  // Update previous to the current state of dp  prev = Arrays.copyOf(curr, n);  }  return curr[n - 1];  }  // Function to calculate the minimum  // Element required to delete for  // Making string palindrome  static int minDeletions(String s) {  int n = s.length();  // Find the LPS   int lps = longestPalinSubseq(s);  return n - lps;  }  public static void main(String[] args) {  String s = "aebcbda";  System.out.println(minDeletions(s));  } }

Python

# Python program to find Minimum number of  # deletions to make a string palindrome # Function to find the length of the lps def longestPalinSubseq(s): n = len(s) # Create two vectors: one for the current state (dp) # and one for the previous state (dpPrev) curr = [0] * n prev = [0] * n # Loop through the string in reverse (starting from the end) for i in range(n - 1, -1, -1): # Initialize the current state of dp curr[i] = 1 # Loop through the characters ahead of i for j in range(i + 1, n): # If the characters at i and j are the same if s[i] == s[j]: # Add 2 to the length of the palindrome between them curr[j] = prev[j - 1] + 2 else: # Take the maximum between excluding either i or j curr[j] = max(prev[j], curr[j - 1]) # Update previous to the current state of dp prev = curr[:] return curr[n - 1] # Function to calculate the minimum # Element required to delete for # Making string palindrome def minDeletions(s): n = len(s) # Find the LPS  lps = longestPalinSubseq(s) return n - lps if __name__ == "__main__": s = "aebcbda" print(minDeletions(s))

// C# program to find Minimum number of  // deletions to make a string palindrome using System; class GfG {  // Function to find the length of the lps  static int longestPalinSubseq(string s) {  int n = s.Length;  // Create two vectors: one for the current state (dp)  // and one for the previous state (dpPrev)  int[] curr = new int[n];  int[] prev = new int[n];  // Loop through the string in reverse (starting from the end)  for (int i = n - 1; i >= 0; --i) {  // Initialize the current state of dp  curr[i] = 1;  // Loop through the characters ahead of i  for (int j = i + 1; j < n; ++j) {  // If the characters at i and j are the same  if (s[i] == s[j]) {  // Add 2 to the length of the palindrome between them  curr[j] = prev[j - 1] + 2;  } else {  // Take the maximum between excluding either i or j  curr[j] = Math.Max(prev[j], curr[j - 1]);  }  }  // Update previous to the current state of dp  Array.Copy(curr, prev, n);  }  return curr[n - 1];  }  // Function to calculate the minimum  // Element required to delete for  // Making string palindrome  static int minDeletions(string s) {  int n = s.Length;  // Find the LPS   int lps = longestPalinSubseq(s);  return n - lps;  }  static void Main(string[] args) {  string s = "aebcbda";  Console.WriteLine(minDeletions(s));  } }

JavaScript

// JavaScript program to find Minimum number of  // deletions to make a string palindrome // Function to find the length of the lps function longestPalinSubseq(s) {  let n = s.length;  // Create two vectors: one for the current state (dp)  // and one for the previous state (dpPrev)  let curr = new Array(n).fill(0);  let prev = new Array(n).fill(0);  // Loop through the string in reverse (starting from the end)  for (let i = n - 1; i >= 0; --i) {  // Initialize the current state of dp  curr[i] = 1;  // Loop through the characters ahead of i  for (let j = i + 1; j < n; ++j) {  // If the characters at i and j are the same  if (s[i] === s[j]) {  // Add 2 to the length of the palindrome between them  curr[j] = prev[j - 1] + 2;  } else {  // Take the maximum between excluding either i or j  curr[j] = Math.max(prev[j], curr[j - 1]);  }  }  // Update previous to the current state of dp  prev = [...curr];  }  return curr[n - 1]; } // Function to calculate the minimum // Element required to delete for // Making string palindrome function minDeletions(s) {  let n = s.length;  // Find the LPS   let lps = longestPalinSubseq(s);  return n - lps; } let s = "aebcbda"; console.log(minDeletions(s));