Given a string of size ‘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 : aebcbda
Output : 2
Remove characters 'e' and 'd'
Resultant string will be 'abcba'
which is a palindromic string
Input : neveropen
Output : 8
A simple solution is to remove all subsequences one by one and check if the remaining string is palindrome or not. The time complexity of this solution is exponential.
- Take two indexes first as ‘i’ and last as a ‘j’
- Compare the character at the index ‘i’ and ‘j’
- If characters are equal, then
- Recursively call the function by incrementing ‘i’ by ‘1’ and decrementing ‘j’ by ‘1’
- else
- Recursively call the two functions, the first increment ‘i’ by ‘1’ keeping ‘j’ constant, second decrement ‘j’ by ‘1’ keeping ‘i’ constant.
- Take a minimum of both and return by adding ‘1’
Below is the implementation of the above approach:
C++
// C++ program for above approach#include <iostream>using namespace std;// Function to return minimum// Element between two valuesint min(int x, int y) { return (x < y) ? x : y; }// Utility function for calculating// Minimum element to deleteint utility_fun_for_del(string str, int i, int j){ if (i >= j) return 0; // Condition to compare characters if (str[i] == str[j]) { // Recursive function call return utility_fun_for_del(str, i + 1, j - 1); } // Return value, incrementing by 1 return 1 + min(utility_fun_for_del(str, i + 1, j), utility_fun_for_del(str, i, j - 1));}// Function to calculate the minimum// Element required to delete for// Making string palindromeint min_ele_del(string str){ // Utility function call return utility_fun_for_del(str, 0, str.length() - 1);}// Driver codeint main(){ string str = "abefbac"; cout << "Minimum element of deletions = " << min_ele_del(str) << endl; return 0;}// This code is contributed by MOHAMMAD MUDASSIR |
Java
// Java program for above approachimport java.io.*;import java.util.*;class GFG{// Function to return minimum// Element between two valuespublic static int min(int x, int y) { return (x < y) ? x : y; } // Utility function for calculating// Minimum element to deletepublic static int utility_fun_for_del(String str, int i, int j){ if (i >= j) return 0; // Condition to compare characters if (str.charAt(i) == str.charAt(j)) { // Recursive function call return utility_fun_for_del(str, i + 1, j - 1); } // Return value, incrementing by 1 return 1 + Math.min(utility_fun_for_del(str, i + 1, j), utility_fun_for_del(str, i, j - 1));} // Function to calculate the minimum// Element required to delete for// Making string palindromepublic static int min_ele_del(String str){ // Utility function call return utility_fun_for_del(str, 0, str.length() - 1);}// Driver Codepublic static void main(String[] args) { String str = "abefbac"; System.out.println("Minimum element of deletions = " + min_ele_del(str));}}// This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program for above approach# Utility function for calculating# Minimum element to deletedef utility_fun_for_del(Str, i, j): if (i >= j): return 0 # Condition to compare characters if (Str[i] == Str[j]): # Recursive function call return utility_fun_for_del(Str, i + 1, j - 1) # Return value, incrementing by 1 # return minimum Element between two values return (1 + min(utility_fun_for_del(Str, i + 1, j), utility_fun_for_del(Str, i, j - 1)))# Function to calculate the minimum# Element required to delete for# Making string palindromedef min_ele_del(Str): # Utility function call return utility_fun_for_del(Str, 0, len(Str) - 1)# Driver codeStr = "abefbac"print("Minimum element of deletions =", min_ele_del(Str))# This code is contributed by avanitrachhadiya2155 |
C#
// C# program for above approachusing System;using System.Collections.Generic; class GFG{ // Function to return minimum// Element between two valuesstatic int min(int x, int y) { return (x < y) ? x : y; } // Utility function for calculating// Minimum element to deletestatic int utility_fun_for_del(string str, int i, int j){ if (i >= j) return 0; // Condition to compare characters if (str[i] == str[j]) { // Recursive function call return utility_fun_for_del(str, i + 1, j - 1); } // Return value, incrementing by 1 return 1 + Math.Min(utility_fun_for_del( str, i + 1, j), utility_fun_for_del( str, i, j - 1));} // Function to calculate the minimum// Element required to delete for// Making string palindromestatic int min_ele_del(string str){ // Utility function call return utility_fun_for_del(str, 0, str.Length - 1);}// Driver code static void Main() { string str = "abefbac"; Console.WriteLine("Minimum element of " + "deletions = " + min_ele_del(str));}}// This code is contributed by divyesh072019 |
Javascript
<script> // Javascript program for above approach // Function to return minimum // Element between two values function min(x, y) { return (x < y) ? x : y; } // Utility function for calculating // Minimum element to delete function utility_fun_for_del(str, i, j) { if (i >= j) return 0; // Condition to compare characters if (str[i] == str[j]) { // Recursive function call return utility_fun_for_del(str, i + 1, j - 1); } // Return value, incrementing by 1 return 1 + Math.min(utility_fun_for_del( str, i + 1, j), utility_fun_for_del( str, i, j - 1)); } // Function to calculate the minimum // Element required to delete for // Making string palindrome function min_ele_del(str) { // Utility function call return utility_fun_for_del(str, 0, str.length - 1); } let str = "abefbac"; document.write("Minimum element of " + "deletions = " + min_ele_del(str));// This code is contributed by mukesh07.</script> |
Output
Minimum element of deletions = 2
Time complexity: O(2^n), the time complexity of this solution is exponential as it requires a recursive approach to solve the problem. There are two recursive calls in each step and hence the time complexity is O(2^n).
Auxiliary Space: O(n), the space complexity of this solution is linear as the recursive calls are stored in the stack frames and the maximum depth of the recursion tree can be n.
Approach: Top-down dynamic programming
Below is the implementation:
C++
#include<bits/stdc++.h>using namespace std;int dp[2000][2000];// Function definitionint transformation(string s1, string s2, int i, int j){ // Base cases if (i >= (s1.size()) || j >= (s2.size())) return 0; // Checking the desired condition if (s1[i] == s2[j]) { // If yes increment the count dp[i][j] = 1 + transformation(s1, s2, i + 1, j + 1); } // If no if (dp[i][j] != -1) { // Return the value from the table return dp[i][j]; } // Else store the max transformation // from the subsequence else dp[i][j] = max(transformation(s1, s2, i, j + i), transformation(s1, s2, i + 1, j)); // Return the dp [-1][-1] return dp[s1.size() - 1][s2.size() - 1];}// Driver codeint main(){ string s1 = "neveropen"; string s2 = "neveropen"; int i = 0; int j = 0; // Initialize the array with -1 memset(dp, -1, sizeof dp); cout << "MINIMUM NUMBER OF DELETIONS: " << (s1.size()) - transformation(s1, s2, 0, 0) << endl; cout << "MINIMUM NUMBER OF INSERTIONS: " << (s2.size()) - transformation(s1, s2, 0, 0) << endl; cout << ("LCS LENGTH: ") << transformation(s1, s2, 0, 0);}// This code is contributed by Stream_Cipher |
Java
import java.util.*;public class GFG{ static int dp[][] = new int[2000][2000]; // Function definition public static int transformation(String s1, String s2, int i, int j) { // Base cases if(i >= s1.length() || j >= s2.length()) { return 0; } // Checking the desired condition if(s1.charAt(i) == s2.charAt(j)) { // If yes increment the count dp[i][j] = 1 + transformation(s1, s2, i + 1, j + 1); } // If no if(dp[i][j] != -1) { // Return the value from the table return dp[i][j]; } // Else store the max transformation // from the subsequence else { dp[i][j] = Math.max(transformation(s1, s2, i, j + i), transformation(s1, s2, i + 1, j)); } // Return the dp [-1][-1] return dp[s1.length() - 1][s2.length() - 1]; } // Driver code public static void main(String []args) { String s1 = "neveropen"; String s2 = "neveropen"; int i = 0; int j = 0; // Initialize the array with -1 for (int[] row: dp) {Arrays.fill(row, -1);} System.out.println("MINIMUM NUMBER OF DELETIONS: " + (s1.length() - transformation(s1, s2, 0, 0))); System.out.println("MINIMUM NUMBER OF INSERTIONS: " + (s2.length() - transformation(s1, s2, 0, 0))); System.out.println("LCS LENGTH: " + transformation(s1, s2, 0, 0)); }}// This code is contributed by avanitrachhadiya2155 |
Python3
# function definitiondef transformation(s1,s2,i,j,dp): # base cases if i>=len(s1) or j>=len(s2): return 0 # checking the desired condition if s1[i]==s2[j]: # if yes increment the count dp[i][j]=1+transformation(s1,s2,i+1,j+1,dp) # if no if dp[i][j]!=-1: #return the value from the table return dp[i][j] # else store the max transformation # from the subsequence else: dp[i][j]=max(transformation(s1,s2,i,j+i,dp), transformation(s1,s2,i+1,j,dp)) # return the dp [-1][-1] return dp[-1][-1] s1 = "neveropen"s2 = "neveropen"i=0j=0#initialize the array with -1dp=[[-1 for _ in range(len(s1)+1)] for _ in range(len(s2)+1)] print("MINIMUM NUMBER OF DELETIONS: ", len(s1)-transformation(s1,s2,0,0,dp), end=" ")print("MINIMUM NUMBER OF INSERTIONS: ", len(s2)-transformation(s1,s2,0,0,dp), end=" " )print("LCS LENGTH: ",transformation(s1,s2,0,0,dp))#code contributed by saikumar kudikala |
C#
using System;class GFG{ static int[,] dp = new int[2000, 2000];// Function definition static int transformation(string s1, string s2, int i, int j ){ // Base cases if (i >= (s1.Length) || j >= (s2.Length)) { return 0; } // Checking the desired condition if (s1[i] == s2[j]) { // If yes increment the count dp[i, j] = 1 + transformation(s1, s2, i + 1, j + 1); } // If no if (dp[i, j] != -1) { // Return the value from the table return dp[i, j]; } // Else store the max transformation // from the subsequence else { dp[i, j] = Math.Max(transformation(s1, s2, i, j + i), transformation(s1, s2, i + 1, j)); } // Return the dp [-1][-1] return dp[s1.Length - 1, s2.Length - 1];}// Driver codestatic public void Main(){ string s1 = "neveropen"; string s2 = "neveropen"; // Initialize the array with -1 for(int m = 0; m < 2000; m++ ) { for(int n = 0; n < 2000; n++) { dp[m, n] = -1; } } Console.WriteLine("MINIMUM NUMBER OF DELETIONS: " + (s1.Length-transformation(s1, s2, 0, 0))); Console.WriteLine("MINIMUM NUMBER OF INSERTIONS: " + (s2.Length-transformation(s1, s2, 0, 0))); Console.WriteLine("LCS LENGTH: " + transformation(s1, s2, 0, 0));}}// This code is contributed by rag2127 |
Javascript
<script>let dp = new Array(2000);// Function definitionfunction transformation(s1, s2, i, j){ // Base cases if(i >= s1.length || j >= s2.length) { return 0; } // Checking the desired condition if (s1[i] == s2[j]) { // If yes increment the count dp[i][j] = 1 + transformation(s1, s2, i + 1, j + 1); } // If no if (dp[i][j] != -1) { // Return the value from the table return dp[i][j]; } // Else store the max transformation // from the subsequence else { dp[i][j] = Math.max(transformation(s1, s2, i, j + i), transformation(s1, s2, i + 1, j)); } // Return the dp [-1][-1] return dp[s1.length - 1][s2.length - 1];}// Driver codelet s1 = "neveropen";let s2 = "neveropen";let i = 0;let j = 0;// Initialize the array with -1for(let row = 0; row < dp.length; row++){ dp[row] = new Array(dp.length); for(let column = 0; column < dp.length; column++) { dp[row][column] = -1; }}document.write("MINIMUM NUMBER OF DELETIONS: " + (s1.length - transformation(s1, s2, 0, 0)));document.write(" MINIMUM NUMBER OF INSERTIONS: " + (s2.length - transformation(s1, s2, 0, 0)));document.write(" LCS LENGTH: " + transformation(s1, s2, 0, 0)); // This code is contributed by rameshtravel07 </script> |
Output:
MINIMUM NUMBER OF DELETIONS: 8 MINIMUM NUMBER OF INSERTIONS: 0 LCS LENGTH: 5
Time Complexity: O(N^K)
Auxiliary Space: O(2000*2000)
Efficient Approach: It uses the concept of finding the length of the longest palindromic subsequence of a given sequence.
Below is the implementation of the approach:
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 deletionsint 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 Codeint main(){ string str = "neveropen"; cout << "Minimum number of deletions = " << minimumNumberOfDeletions(str); return 0;} |
Java
// Java implementation to // find minimum number of // deletions to make a // string palindromicclass 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 = "neveropen"; System.out.println("Minimum number " + "of deletions = "+ minimumNumberOfDeletions(str)); }}// This code is contributed by Sumit Ghosh |
Python3
# Python3 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 deletionsdef 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 Codeif __name__ == "__main__": str = "neveropen" print( "Minimum number of deletions = " , minimumNumberOfDeletions(str)) |
C#
// C# implementation to find // minimum number of deletions// to make a string palindromicusing 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 = "neveropen"; Console.Write("Minimum number of" + " deletions = " + minimumNumberOfDeletions(str)); }}// This code is contributed by nitin mittal. |
Javascript
<script> // JavaScript implementation to // find minimum number of // deletions to make a // string palindromic // Returns the length of // the longest palindromic // subsequence in 'str' function lps(str) { let n = str.length; // Create a table to store // results of subproblems let L = new Array(n); for (let i = 0; i < n; i++) { L[i] = new Array(n); for (let j = 0; j < n; j++) { L[i][j] = 0; } } // Strings of length 1 // are palindrome of length 1 for (let 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 (let cl = 2; cl <= n; cl++) { for (let i = 0; i < n - cl + 1; i++) { let 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 function minimumNumberOfDeletions(str) { let n = str.length; // Find longest palindromic // subsequence let len = lps(str); // After removing characters // other than the lps, we get // palindrome. return (n - len); } let str = "neveropen"; document.write("Minimum number " + "of deletions = "+ minimumNumberOfDeletions(str)); </script> |
PHP
<?php// PHP implementation to find // minimum number of deletions// to make a string palindromic// Returns the length of// the longest palindromic// subsequence in 'str'function lps($str){ $n = strlen($str); // Create a table to store // results of subproblems $L; // Strings of length 1 // are palindrome of length 1 for ($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 ($cl = 2; $cl <= $n; $cl++) { for ( $i = 0; $i < $n -$cl + 1; $i++) { $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 deletionsfunction minimumNumberOfDeletions($str){ $n = strlen($str); // Find longest // palindromic subsequence $len = lps($str); // After removing characters // other than the lps, we get // palindrome. return ($n - $len);}// Driver Code{ $str = "neveropen"; echo "Minimum number of deletions = ", minimumNumberOfDeletions($str); return 0;}// This code is contributed by nitin mittal.?> |
Output
Minimum number of deletions = 8
Time Complexity: O(n^2),as the LPS subproblem is solved using dynamic programming.
Auxiliary Space: O(n^2) as a 2D array of size nxn is used to store the subproblems.
Efficient Approach: Space optimization
In the previous approach, the current value dp[i][j] only depends upon the current and previous row values of DP. So to optimize the space complexity we use a single 1D array to store the computations.
Implementation:
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(); // array to store computation // of subproblems int L[n]; // iterate over subproblems to get the current // value from previous computation for (int i = n - 1; i >= 0; i--) { // to store previous values int back_up = 0; for (int j = i; j < n; j++) { if (j == i) L[j] = 1; else if (str[i] == str[j]) { int temp = L[j]; L[j] = back_up + 2; back_up = temp; } else { back_up = L[j]; L[j] = max(L[j], L[j - 1]); } } } // return final answer return L[n - 1];} // function to calculate // minimum number of deletionsint 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 Codeint main(){ string str = "neveropen"; cout << "Minimum number of deletions = " << minimumNumberOfDeletions(str); return 0;}// -- by bhardwajji |
Java
public class Main { // Returns the length of the longest palindromic subsequence in 'str' static int lps(String str) { int n = str.length(); // Array to store computation of subproblems int[] L = new int[n]; // Iterate over subproblems to get the current value from previous computation for (int i = n - 1; i >= 0; i--) { // To store previous values int back_up = 0; for (int j = i; j < n; j++) { if (j == i) L[j] = 1; else if (str.charAt(i) == str.charAt(j)) { int temp = L[j]; L[j] = back_up + 2; back_up = temp; } else { back_up = L[j]; L[j] = Math.max(L[j], L[j - 1]); } } } // Return final answer return L[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 a palindrome. return (n - len); } // Driver Code public static void main(String[] args) { String str = "neveropen"; System.out.println("Minimum number of deletions = " + minimumNumberOfDeletions(str)); }}// This code is contributed by rambabuguphka |
C#
using System;class Program{ // Returns the length of // the longest palindromic // subsequence in 'str' static int LPS(string str) { int n = str.Length; // array to store computation // of subproblems int[] L = new int[n]; // iterate over subproblems to get the current // value from previous computation for (int i = n - 1; i >= 0; i--) { // to store previous values int back_up = 0; for (int j = i; j < n; j++) { if (j == i) L[j] = 1; else if (str[i] == str[j]) { int temp = L[j]; L[j] = back_up + 2; back_up = temp; } else { back_up = L[j]; L[j] = Math.Max(L[j], L[j - 1]); } } } // return final answer return L[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 static void Main() { string str = "neveropen"; Console.WriteLine("Minimum number of deletions = " + MinimumNumberOfDeletions(str)); }} |
Javascript
// Function to calculate the length of the longest palindromic subsequence in 'str'function lps(str) { const n = str.length; // Array to store computation of subproblems const L = new Array(n).fill(0); // Iterate over subproblems to get the current value from previous computation for (let i = n - 1; i >= 0; i--) { // To store previous values let back_up = 0; for (let j = i; j < n; j++) { if (j === i) { L[j] = 1; } else if (str[i] === str[j]) { const temp = L[j]; L[j] = back_up + 2; back_up = temp; } else { back_up = L[j]; L[j] = Math.max(L[j], L[j - 1]); } } } // Return final answer return L[n - 1];}// Function to calculate the minimum number of deletionsfunction minimumNumberOfDeletions(str) { const n = str.length; // Find longest palindromic subsequence const len = lps(str); // After removing characters other than the lps, we get palindrome. return n - len;}// Driver Codeconst str = "neveropen";console.log("Minimum number of deletions =", minimumNumberOfDeletions(str)); |
Output
Minimum number of deletions = 8
Time Complexity: O(n^2).
Auxiliary Space: O(n)
If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
