Dada una string de tamaño ‘n’. La tarea es eliminar o eliminar el número mínimo de caracteres de la string para que la string resultante sea un palíndromo.
Nota: Se debe mantener el orden de los caracteres.
Ejemplos:
Input : aebcbda Output : 2 Remove characters 'e' and 'd' Resultant string will be 'abcba' which is a palindromic string Input : geeksforgeeks Output : 8
Una solución simple es eliminar todas las subsecuencias una por una y verificar si la string restante es palíndromo o no. La complejidad temporal de esta solución es exponencial.
Un enfoque eficiente utiliza el concepto de encontrar la longitud de la subsecuencia palindrómica más larga de una secuencia dada.
Algoritmo:
1. str es la string dada.
2. n longitud de str
3. len sea la longitud de la
subsecuencia palindrómica más larga de str
4. número mínimo de eliminaciones
min = n – len
A continuación se muestra la implementación del enfoque anterior:
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 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
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 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
<?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 deletions
function 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 = "geeksforgeeks";
echo "Minimum number of deletions = ",
minimumNumberOfDeletions($str);
return 0;
}
// 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 = "geeksforgeeks";
document.write("Minimum number " + "of deletions = "+
minimumNumberOfDeletions(str));
</script>
Producción
Minimum number of deletions = 8
Complejidad temporal: O(n 2 )
Otro enfoque:
- Tome dos índices primero como ‘i’ y último como ‘j’
- ahora compare el carácter en el índice ‘i’ y ‘j’
- si los caracteres son iguales, entonces
- llame recursivamente a la función incrementando ‘i’ en ‘1’ y disminuyendo ‘j’ en ‘1’
- más
- llama recursivamente a las dos funciones, la primera incrementa ‘i’ en ‘1’ manteniendo ‘j’ constante, la segunda decrementa ‘j’ en ‘1’ manteniendo ‘i’ constante.
- tome un mínimo de ambos y regrese agregando ‘1’
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for above approach
#include <iostream>
using namespace std;
// Function to return minimum
// Element between two values
int min(int x, int y)
{
return (x < y) ? x : y;
}
// Utility function for calculating
// Minimum element to delete
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 + 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
int min_ele_del(string str)
{
// Utility function call
return utility_fun_for_del(str, 0,
str.length() - 1);
}
// Driver code
int 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 approach
import java.io.*;
import java.util.*;
class GFG{
// Function to return minimum
// Element between two values
public static int min(int x, int y)
{
return (x < y) ? x : y;
}
// Utility function for calculating
// Minimum element to delete
public 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 palindrome
public static int min_ele_del(String str)
{
// Utility function call
return utility_fun_for_del(str, 0,
str.length() - 1);
}
// Driver Code
public 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 delete
def 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 palindrome
def min_ele_del(Str):
# Utility function call
return utility_fun_for_del(Str, 0,
len(Str) - 1)
# Driver code
Str = "abefbac"
print("Minimum element of deletions =",
min_ele_del(Str))
# This code is contributed by avanitrachhadiya2155
C#
// C# program for above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to return minimum
// Element between two values
static int min(int x, int y)
{
return (x < y) ? x : y;
}
// Utility function for calculating
// Minimum element to delete
static 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 palindrome
static 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>
Producción
Minimum element of deletions = 2
Enfoque: Programación dinámica de arriba hacia abajo
Primero definiremos la tabla DP y la inicializaremos con -1 en toda la tabla. Siga el siguiente enfoque ahora,
- Defina la función de transformación para calcular el número mínimo de eliminaciones e inserciones para transformar una string en otra
- Escribimos la condición para los casos base.
- Comprobación de la condición deseada
- Si se cumple la condición incrementamos el valor y almacenamos el valor en la tabla
- Si la llamada recursiva se resuelve antes, utilizamos directamente el valor de la tabla
- De lo contrario, almacene la transformación máxima de la subsecuencia
- Continuaremos el proceso hasta llegar a la condición base.
- Devolver el PD [-1][-1]
A continuación se muestra la implementación:
C++
#include<bits/stdc++.h>
using namespace std;
int dp[2000][2000];
// Function definition
int transformation(string s1, string s2,
int i, int j)
{
// Base cases
if (i >= (s1.size()) || j >= (s2.size()))
return 0;
// Checking the ndesired 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 form 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 code
int main()
{
string s1 = "geeksforgeeks";
string s2 = "geeks";
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 ndesired 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 form 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 = "geeksforgeeks";
String s2 = "geeks";
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 definition
def transformation(s1,s2,i,j,dp):
# base cases
if i>=len(s1) or j>=len(s2):
return 0
# checking the ndesired 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 form 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 = "geeksforgeeks"
s2 = "geeks"
i=0
j=0
#initialize the array with -1
dp=[[-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 ndesired 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 form 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
static public void Main()
{
string s1 = "geeksforgeeks";
string s2 = "geeks";
// 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 definition
function transformation(s1, s2, i, j)
{
// Base cases
if(i >= s1.length || j >= s2.length)
{
return 0;
}
// Checking the ndesired 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 form 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
let s1 = "geeksforgeeks";
let s2 = "geeks";
let i = 0;
let j = 0;
// Initialize the array with -1
for(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>
Producción:
MINIMUM NUMBER OF DELETIONS: 8 MINIMUM NUMBER OF INSERTIONS: 0 LCS LENGTH: 5
Complejidad de tiempo: O(N^K)
Complejidad espacial: O(N)
Este artículo es una contribución de Ayush Jauhari .
Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA