Dada una secuencia, encuentre la longitud de la subsecuencia palindrómica más larga en ella.
Como otro ejemplo, si la secuencia dada es «BBABCBCAB», entonces la salida debería ser 7 ya que «BABCBAB» es la subsecuencia palindrómica más larga en ella. “BBBBB” y “BBCBB” también son subsecuencias palindrómicas de la secuencia dada, pero no las más largas.
La solución ingenua para este problema es generar todas las subsecuencias de la secuencia dada y encontrar la subsecuencia palindrómica más larga. Esta solución es exponencial en términos de complejidad temporal. Veamos cómo este problema posee las dos propiedades importantes de un problema de programación dinámica (DP) y puede resolverse de manera eficiente utilizando la programación dinámica.
1) Subestructura óptima:
Sea X[0..n-1] la secuencia de entrada de longitud n y L(0, n-1) la longitud de la subsecuencia palindrómica más larga de X[0..n-1].
Si el último y el primer carácter de X son iguales, entonces L(0, n-1) = L(1, n-2) + 2. De
lo contrario, L(0, n-1) = MAX (L(1, n-1 ), L(0, n-2)).
Lo que sigue es una solución recursiva general con todos los casos manejados.
// Every single character is a palindrome of length 1
L(i, i) = 1 for all indexes i in given sequence
// IF first and last characters are not same
If (X[i] != X[j]) L(i, j) = max{L(i + 1, j),L(i, j - 1)}
// If there are only 2 characters and both are same
Else if (j == i + 1) L(i, j) = 2
// If there are more than two characters, and first and last
// characters are same
Else L(i, j) = L(i + 1, j - 1) + 2
2) Subproblemas superpuestos: a continuación se muestra una implementación recursiva simple del problema LPS. La implementación simplemente sigue la estructura recursiva mencionada anteriormente.
C++
// C++ program of above approach
#include<bits/stdc++.h>
using namespace std;
// A utility function to get max of two integers
int max (int x, int y) { return (x > y)? x : y; }
// Returns the length of the longest palindromic subsequence in seq
int lps(char *seq, int i, int j)
{
// Base Case 1: If there is only 1 character
if (i == j)
return 1;
// Base Case 2: If there are only 2
// characters and both are same
if (seq[i] == seq[j] && i + 1 == j)
return 2;
// If the first and last characters match
if (seq[i] == seq[j])
return lps (seq, i+1, j-1) + 2;
// If the first and last characters do not match
return max( lps(seq, i, j-1), lps(seq, i+1, j) );
}
/* Driver program to test above functions */
int main()
{
char seq[] = "GEEKSFORGEEKS";
int n = strlen(seq);
cout << "The length of the LPS is "
<< lps(seq, 0, n-1);
return 0;
}
// This code is contributed
// by Akanksha Rai
C
// C program of above approach
#include<stdio.h>
#include<string.h>
// A utility function to get max of two integers
int max (int x, int y) { return (x > y)? x : y; }
// Returns the length of the longest palindromic subsequence in seq
int lps(char *seq, int i, int j)
{
// Base Case 1: If there is only 1 character
if (i == j)
return 1;
// Base Case 2: If there are only 2 characters and both are same
if (seq[i] == seq[j] && i + 1 == j)
return 2;
// If the first and last characters match
if (seq[i] == seq[j])
return lps (seq, i+1, j-1) + 2;
// If the first and last characters do not match
return max( lps(seq, i, j-1), lps(seq, i+1, j) );
}
/* Driver program to test above functions */
int main()
{
char seq[] = "GEEKSFORGEEKS";
int n = strlen(seq);
printf ("The length of the LPS is %d", lps(seq, 0, n-1));
getchar();
return 0;
}
Java
//Java program of above approach
class GFG {
// A utility function to get max of two integers
static int max(int x, int y) {
return (x > y) ? x : y;
}
// Returns the length of the longest palindromic subsequence in seq
static int lps(char seq[], int i, int j) {
// Base Case 1: If there is only 1 character
if (i == j) {
return 1;
}
// Base Case 2: If there are only 2 characters and both are same
if (seq[i] == seq[j] && i + 1 == j) {
return 2;
}
// If the first and last characters match
if (seq[i] == seq[j]) {
return lps(seq, i + 1, j - 1) + 2;
}
// If the first and last characters do not match
return max(lps(seq, i, j - 1), lps(seq, i + 1, j));
}
/* Driver program to test above function */
public static void main(String[] args) {
String seq = "GEEKSFORGEEKS";
int n = seq.length();
System.out.printf("The length of the LPS is %d", lps(seq.toCharArray(), 0, n - 1));
}
}
Python3
# Python 3 program of above approach
# A utility function to get max
# of two integers
def max(x, y):
if(x > y):
return x
return y
# Returns the length of the longest
# palindromic subsequence in seq
def lps(seq, i, j):
# Base Case 1: If there is
# only 1 character
if (i == j):
return 1
# Base Case 2: If there are only 2
# characters and both are same
if (seq[i] == seq[j] and i + 1 == j):
return 2
# If the first and last characters match
if (seq[i] == seq[j]):
return lps(seq, i + 1, j - 1) + 2
# If the first and last characters
# do not match
return max(lps(seq, i, j - 1),
lps(seq, i + 1, j))
# Driver Code
if __name__ == '__main__':
seq = "GEEKSFORGEEKS"
n = len(seq)
print("The length of the LPS is",
lps(seq, 0, n - 1))
# This code contributed by Rajput-Ji
C#
// C# program of the above approach
using System;
public class GFG{
// A utility function to get max of two integers
static int max(int x, int y) {
return (x > y) ? x : y;
}
// Returns the length of the longest palindromic subsequence in seq
static int lps(char []seq, int i, int j) {
// Base Case 1: If there is only 1 character
if (i == j) {
return 1;
}
// Base Case 2: If there are only 2 characters and both are same
if (seq[i] == seq[j] && i + 1 == j) {
return 2;
}
// If the first and last characters match
if (seq[i] == seq[j]) {
return lps(seq, i + 1, j - 1) + 2;
}
// If the first and last characters do not match
return max(lps(seq, i, j - 1), lps(seq, i + 1, j));
}
/* Driver program to test above function */
public static void Main() {
String seq = "GEEKSFORGEEKS";
int n = seq.Length;
Console.Write("The length of the LPS is "+lps(seq.ToCharArray(), 0, n - 1));
}
}
// This code is contributed by Rajput-Ji
PHP
<?php
// PHP program of above approach
// Returns the length of the longest
// palindromic subsequence in seq
function lps($seq, $i, $j)
{
// Base Case 1: If there is
// only 1 character
if ($i == $j)
return 1;
// Base Case 2: If there are only 2
// characters and both are same
if ($seq[$i] == $seq[$j] && $i + 1 == $j)
return 2;
// If the first and last characters match
if ($seq[$i] == $seq[$j])
return lps ($seq, $i + 1, $j - 1) + 2;
// If the first and last characters
// do not match
return max(lps($seq, $i, $j - 1),
lps($seq, $i + 1, $j));
}
// Driver Code
$seq = "GEEKSFORGEEKS";
$n = strlen($seq);
echo "The length of the LPS is ".
lps($seq, 0, $n - 1);
// This code is contributed by ita_c
?>
Javascript
<script>
// A utility function to get max of two integers
function max(x, y)
{
return (x > y) ? x : y;
}
// Returns the length of the longest palindromic subsequence in seq
function lps(seq, i, j)
{
// Base Case 1: If there is only 1 character
if (i == j)
{
return 1;
}
// Base Case 2: If there are only 2 characters and both are same
if (seq[i] == seq[j] && i + 1 == j)
{
return 2;
}
// If the first and last characters match
if (seq[i] == seq[j])
{
return lps(seq, i + 1, j - 1) + 2;
}
// If the first and last characters do not match
return max(lps(seq, i, j - 1), lps(seq, i + 1, j));
}
/* Driver program to test above function */
let seq = "GEEKSFORGEEKS";
let n = seq.length;
document.write("The length of the LPS is ", lps(seq.split(""), 0, n - 1));
// This code is contributed by avanitrachhadiya2155
</script>
Producción
The length of the LPS is 5
Teniendo en cuenta la implementación anterior, el siguiente es un árbol de recurrencia parcial para una secuencia de longitud 6 con todos los caracteres diferentes.
L(0, 5)
/ \
/ \
L(1,5) L(0,4)
/ \ / \
/ \ / \
L(2,5) L(1,4) L(1,4) L(0,3)
En el árbol de recursión parcial anterior, L(1, 4) se resuelve dos veces. Si dibujamos el árbol de recursión completo, podemos ver que hay muchos subproblemas que se resuelven una y otra vez. Dado que se vuelven a llamar los mismos subproblemas, este problema tiene la propiedad Superposición de subproblemas. Entonces, el problema LPS tiene ambas propiedades (ver this y this ) de un problema de programación dinámica. Al igual que otros problemas típicos de programación dinámica (DP) , los cálculos de los mismos subproblemas se pueden evitar mediante la construcción de una array temporal L[][] de forma ascendente.
3) Solución de programación dinámica:
C++
// A Dynamic Programming based C++ program for LPS problem
// Returns the length of the longest palindromic subsequence in seq
#include<stdio.h>
#include<string.h>
// A utility function to get max of two integers
int max (int x, int y) { return (x > y)? x : y; }
// Returns the length of the longest palindromic subsequence in seq
int lps(char *str)
{
int n = strlen(str);
int i, j, cl;
int L[n][n]; // Create a table to store results of subproblems
// 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. The values are filled in a
// manner similar to Matrix Chain Multiplication DP solution (See
// https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/). cl 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]);
}
}
return L[0][n-1];
}
/* Driver program to test above functions */
int main()
{
char seq[] = "GEEKSFORGEEKS";
int n = strlen(seq);
printf ("The length of the LPS is %d", lps(seq));
getchar();
return 0;
}
Java
// A Dynamic Programming based Java
// Program for the Egg Dropping Puzzle
class LPS
{
// A utility function to get max of two integers
static int max (int x, int y) { return (x > y)? x : y; }
// Returns the length of the longest
// palindromic subsequence in seq
static int lps(String seq)
{
int n = seq.length();
int i, j, cl;
// Create a table to store results of subproblems
int L[][] = new int[n][n];
// 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.
// The values are filled in a manner similar
// to Matrix Chain Multiplication DP solution (See
// https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/).
// cl is length of substring
for (cl=2; cl<=n; cl++)
{
for (i=0; i<n-cl+1; i++)
{
j = i+cl-1;
if (seq.charAt(i) == seq.charAt(j) && cl == 2)
L[i][j] = 2;
else if (seq.charAt(i) == seq.charAt(j))
L[i][j] = L[i+1][j-1] + 2;
else
L[i][j] = max(L[i][j-1], L[i+1][j]);
}
}
return L[0][n-1];
}
/* Driver program to test above functions */
public static void main(String args[])
{
String seq = "GEEKSFORGEEKS";
int n = seq.length();
System.out.println("The length of the LPS is "+ lps(seq));
}
}
/* This code is contributed by Rajat Mishra */
Python3
// A Dynamic Programming based Java
// Program for the Egg Dropping Puzzle
class LPS
{
// A utility function to get max of two integers
static int max (int x, int y) { return (x > y)? x : y; }
// Returns the length of the longest
// palindromic subsequence in seq
static int lps(String seq)
{
int n = seq.length();
int i, j, cl;
// Create a table to store results of subproblems
int L[][] = new int[n][n];
// 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.
// The values are filled in a manner similar
// to Matrix Chain Multiplication DP solution (See
// https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/).
// cl is length of substring
for (cl=2; cl<=n; cl++)
{
for (i=0; i<n-cl+1; i++)
{
j = i+cl-1;
if (seq.charAt(i) == seq.charAt(j) && cl == 2)
L[i][j] = 2;
else if (seq.charAt(i) == seq.charAt(j))
L[i][j] = L[i+1][j-1] + 2;
else
L[i][j] = max(L[i][j-1], L[i+1][j]);
}
}
return L[0][n-1];
}
/* Driver program to test above functions */
public static void main(String args[])
{
String seq = "GEEKSFORGEEKS";
int n = seq.length();
System.out.println("The length of the lps is "+ lps(seq));
}
}
/* This code is contributed by Rajat Mishra */
C#
// A Dynamic Programming based C# Program
// for the Egg Dropping Puzzle
using System;
class GFG {
// A utility function to get max of
// two integers
static int max (int x, int y)
{
return (x > y)? x : y;
}
// Returns the length of the longest
// palindromic subsequence in seq
static int lps(string seq)
{
int n = seq.Length;
int i, j, cl;
// Create a table to store results
// of subproblems
int [,]L = new int[n,n];
// 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. The values are
// filled in a manner similar to
// Matrix Chain Multiplication DP
// solution (See
// https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/
// cl is length of substring
for (cl = 2; cl <= n; cl++)
{
for (i = 0; i < n-cl+1; i++)
{
j = i + cl - 1;
if (seq[i] == seq[j] &&
cl == 2)
L[i,j] = 2;
else if (seq[i] == seq[j])
L[i,j] = L[i+1,j-1] + 2;
else
L[i,j] =
max(L[i,j-1], L[i+1,j]);
}
}
return L[0,n-1];
}
/* Driver program to test above
functions */
public static void Main()
{
string seq = "GEEKSFORGEEKS";
int n = seq.Length;
Console.Write("The length of the "
+ "LPS is "+ lps(seq));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// A Dynamic Programming based
// PHP program for LPS problem
// Returns the length of the
// longest palindromic
// subsequence in seq
// A utility function to get
// max of two integers
// function max( $x, $y)
// { return ($x > $y)? $x : $y; }
// Returns the length of the
// longest palindromic
// subsequence in seq
function lps($str)
{
$n = strlen($str);
$i; $j; $cl;
// Create a table to store
// results of subproblems
$L[][] = array(array());
// 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.
// The values are filled in a
// manner similar to Matrix
// Chain Multiplication DP
// solution (See
// https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/).
// cl 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]);
}
}
return $L[0][$n - 1];
}
// Driver Code
$seq = 'GEEKSFORGEEKS';
$n = strlen($seq);
echo "The length of the " .
"LPS is ", lps($seq);
// This code is contributed
// by shiv_bhakt.
?>
Javascript
<script>
// A Dynamic Programming based Javascript
// Program for the Egg Dropping Puzzle
// A utility function to get max of two integers
function max(x,y)
{
return (x > y)? x : y;
}
// Returns the length of the longest
// palindromic subsequence in seq
function lps(seq)
{
let n = seq.length;
let i, j, cl;
// Create a table to store results of subproblems
let L = new Array(n);
for(let x=0;x<n;x++)
{
L[x] = new Array(n);
for(let y = 0; y < n; y++)
L[x][y] = 0;
}
// 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.
// The values are filled in a manner similar
// to Matrix Chain Multiplication DP solution (See
// https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/).
// cl is length of substring
for (cl = 2; cl <= n; cl++)
{
for (i = 0; i < n -cl + 1; i++)
{
j = i + cl - 1;
if (seq[i] == seq[j] && cl == 2)
L[i][j] = 2;
else if (seq[i] == seq[j])
L[i][j] = L[i + 1][j - 1] + 2;
else
L[i][j] = max(L[i][j - 1], L[i + 1][j]);
}
}
return L[0][n - 1];
}
/* Driver program to test above functions */
let seq = "GEEKSFORGEEKS";
let n = seq.length;
document.write("The length of the lps is "+ lps(seq));
// This code is contributed by rag2127
</script>
Producción
The length of the LPS is 5
Complejidad de tiempo: O(n^2), que es mucho mejor que la complejidad de tiempo en el peor de los casos de la implementación recursiva ingenua.
Uso de la técnica de memorización de la programación dinámica: la idea utilizada aquí es invertir la string de entrada dada y verificar la longitud de la subsecuencia común más larga . Esa sería la respuesta para la subsecuencia palindrómica más larga.
C++
// A Dynamic Programming based C++ program for LPS problem
// Returns the length of the longest palindromic subsequence
// in seq
#include <bits/stdc++.h>
using namespace std;
int dp[1001][1001];
// Returns the length of the longest palindromic subsequence
// in seq
int lps(string& s1, string& s2, int n1, int n2)
{
if (n1 == 0 || n2 == 0) {
return 0;
}
if (dp[n1][n2] != -1) {
return dp[n1][n2];
}
if (s1[n1 - 1] == s2[n2 - 1]) {
return dp[n1][n2] = 1 + lps(s1, s2, n1 - 1, n2 - 1);
}
else {
return dp[n1][n2] = max(lps(s1, s2, n1 - 1, n2),
lps(s1, s2, n1, n2 - 1));
}
}
/* Driver program to test above functions */
int main()
{
string seq = "GEEKSFORGEEKS";
int n = seq.size();
dp[n][n];
memset(dp, -1, sizeof(dp));
string s2 = seq;
reverse(s2.begin(), s2.end());
cout << "The length of the LPS is "
<< lps(s2, seq, n, n) << endl;
return 0;
}
// This code is contributed by Arun Bang
Java
// Java program of above approach
import java.util.*;
class GFG {
// A utility function to get max of two integers
static int max(int x, int y) { return (x > y) ? x : y; }
// Returns the length of the longest palindromic
// subsequence in seq
static int lps(char seq[], int i, int j, int dp[][])
{
// Base Case 1: If there is only 1 character
if (i == j) {
return dp[i][j] = 1;
}
// Base Case 2: If there are only 2 characters and
// both are same
if (seq[i] == seq[j] && i + 1 == j) {
return dp[i][j] = 2;
}
// If the first and last characters match
if (seq[i] == seq[j]) {
return dp[i][j] = lps(seq, i + 1, j - 1, dp) + 2;
}
// If the first and last characters do not match
return dp[i][j] = max(lps(seq, i, j - 1, dp), lps(seq, i + 1, j, dp));
}
/* Driver program to test above function */
public static void main(String[] args)
{
String seq = "GEEKSFORGEEKS";
int n = seq.length();
int dp[][] = new int[n][n];
for(int[] arr: dp)
Arrays.fill(arr, -1);
System.out.printf("The length of the LPS is %d",
lps(seq.toCharArray(), 0, n - 1, dp));
}
}
// This code is contributed by gauravrajput1
Python3
# A Dynamic Programming based Python program for LPS problem
# Returns the length of the longest palindromic subsequence
# in seq
dp = [[-1 for i in range(1001)]for j in range(1001)]
# Returns the length of the longest palindromic subsequence
# in seq
def lps(s1, s2, n1, n2):
if (n1 == 0 or n2 == 0):
return 0
if (dp[n1][n2] != -1):
return dp[n1][n2]
if (s1[n1 - 1] == s2[n2 - 1]):
dp[n1][n2] = 1 + lps(s1, s2, n1 - 1, n2 - 1)
return dp[n1][n2]
else:
dp[n1][n2] = max(lps(s1, s2, n1 - 1, n2), lps(s1, s2, n1, n2 - 1))
return dp[n1][n2]
# Driver program to test above functions
seq = "GEEKSFORGEEKS"
n = len(seq)
s2 = seq
s2 = s2[::-1]
print(f"The length of the LPS is {lps(s2, seq, n, n)}")
# This code is contributed by shinjanpatra
C#
// C# code to implement the approach
using System;
using System.Numerics;
using System.Collections.Generic;
public class GFG {
// A utility function to get max of two integers
static int max(int x, int y) { return (x > y) ? x : y; }
// Returns the length of the longest palindromic
// subsequence in seq
static int lps(char[] seq, int i, int j)
{
// Base Case 1: If there is only 1 character
if (i == j) {
return 1;
}
// Base Case 2: If there are only 2 characters and
// both are same
if (seq[i] == seq[j] && i + 1 == j) {
return 2;
}
// If the first and last characters match
if (seq[i] == seq[j]) {
return lps(seq, i + 1, j - 1) + 2;
}
// If the first and last characters do not match
return max(lps(seq, i, j - 1), lps(seq, i + 1, j));
}
// Driver Code
public static void Main(string[] args)
{
string seq = "GEEKSFORGEEKS";
int n = seq.Length;
Console.Write("The length of the LPS is "
+ lps(seq.ToCharArray(), 0, n - 1));
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// A Dynamic Programming based JavaScript program for LPS problem
// Returns the length of the longest palindromic subsequence
// in seq
let dp;
// Returns the length of the longest palindromic subsequence
// in seq
function lps(s1, s2, n1, n2)
{
if (n1 == 0 || n2 == 0) {
return 0;
}
if (dp[n1][n2] != -1) {
return dp[n1][n2];
}
if (s1[n1 - 1] == s2[n2 - 1]) {
return dp[n1][n2] = 1 + lps(s1, s2, n1 - 1, n2 - 1);
}
else {
return dp[n1][n2] = Math.max(lps(s1, s2, n1 - 1, n2),
lps(s1, s2, n1, n2 - 1));
}
}
/* Driver program to test above functions */
let seq = "GEEKSFORGEEKS";
let n = seq.length;
dp = new Array(1001);
for(let i=0;i<1001;i++){
dp[i] = new Array(1001).fill(-1);
}
let s2 = seq;
s2 = s2.split('').reverse().join('');
document.write("The length of the LPS is " + lps(s2, seq, n, n),"</br>");
// This code is contributed by shinjanpatra
</script>
Producción
The length of the LPS is 5
Complejidad Temporal: O(n 2 )
Espacio Auxiliar: (n 2 )
Imprimir subsecuencia palindrómica más larga Subsecuencia palindrómica más larga con espacio O(n) Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema discutido anteriormente. Referencias: http://users.eecs.northwestern.edu/~dda902/336/hw6-sol.pdf
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