Cuente todas las subsecuencias palindrómicas en una string dada

Encuentre cuántas subsecuencias palindrómicas (no necesariamente deben ser distintas) se pueden formar en una string dada. Tenga en cuenta que la string vacía no se considera un palíndromo. 

Ejemplos: 

Input : str = "abcd"
Output : 4
Explanation :- palindromic  subsequence are : "a" ,"b", "c" ,"d" 

Input : str = "aab"
Output : 4
Explanation :- palindromic subsequence are :"a", "a", "b", "aa"

Input : str = "aaaa"
Output : 15

El problema anterior se puede definir recursivamente. 

Initial Values : i= 0, j= n-1;

CountPS(i,j)
// Every single character of a string is a palindrome 
// subsequence 
if i == j
   return 1 // palindrome of length 1

// If first and last characters are same, then we 
// consider it as palindrome subsequence and check
// for the rest subsequence (i+1, j), (i, j-1)
Else if (str[i] == str[j])
   return   countPS(i+1, j) + countPS(i, j-1) + 1;

else
   // check for rest sub-sequence and  remove common
   // palindromic subsequences as they are counted
   // twice when we do countPS(i+1, j) + countPS(i,j-1)
   return countPS(i+1, j) + countPS(i, j-1) - countPS(i+1, j-1)

Explanation of Recurisive Solution to Counting Palindromic Subsequence

Si dibujamos el árbol de recurrencia de la solución recursiva anterior, podemos observar subproblemas superpuestos . Dado que el problema tiene subproblemas superpuestos, podemos resolverlo de manera eficiente utilizando Programación Dinámica. A continuación se muestra una solución basada en programación dinámica.

Ejemplo 

C++

// Counts Palindromic Subsequence in a given String
#include <cstring>
#include <iostream>
using namespace std;
 
// Function return the total palindromic subsequence
int countPS(string str)
{
    int N = str.length();
 
    // create a 2D array to store the count of palindromic
    // subsequence
    int cps[N + 1][N + 1];
    memset(cps, 0, sizeof(cps));
 
    // palindromic subsequence of length 1
    for (int i = 0; i < N; i++)
        cps[i][i] = 1;
 
    // check subsequence of length L is palindrome or not
    for (int L = 2; L <= N; L++) {
        for (int i = 0; i <= N-L; i++) {
            int k = L + i - 1;
            if (str[i] == str[k])
                cps[i][k]
                    = cps[i][k - 1] + cps[i + 1][k] + 1;
            else
                cps[i][k] = cps[i][k - 1] + cps[i + 1][k]
                            - cps[i + 1][k - 1];
        }
    }
 
    // return total palindromic subsequence
    return cps[0][N - 1];
}
 
// Driver program
int main()
{
    string str = "abcb";
    cout << "Total palindromic subsequence are : "
         << countPS(str) << endl;
    return 0;
}

Java

// Java code to Count Palindromic Subsequence
// in a given String
public class GFG {
    // Function return the total palindromic
    // subsequence
    static int countPS(String str)
    {
        int N = str.length();
 
        // create a 2D array to store the count
        // of palindromic subsequence
        int[][] cps = new int[N][N];
 
        // palindromic subsequence of length 1
        for (int i = 0; i < N; i++)
            cps[i][i] = 1;
 
        // check subsequence of length L is
        // palindrome or not
        for (int L = 2; L <= N; L++) {
            for (int i = 0; i <= N-L; i++) {
                int k = L + i - 1;
              if (str.charAt(i) == str.charAt(k)) {
                cps[i][k] = cps[i][k - 1]
                                    + cps[i + 1][k] + 1;
              }else{
                cps[i][k] = cps[i][k - 1]
                                    + cps[i + 1][k]
                                    - cps[i + 1][k - 1];
              }
            }
        }
 
        // return total palindromic subsequence
        return cps[0][N - 1];
    }
 
    // Driver program
    public static void main(String args[])
    {
        String str = "abcb";
        System.out.println("Total palindromic "
                           + "subsequence are : "
                           + countPS(str));
    }
}
// This code is contributed by Sumit Ghosh

Python3

# Python3 code to Count Palindromic
# Subsequence in a given String
 
# Function return the total
# palindromic subsequence
 
 
def countPS(str):
 
    N = len(str)
 
    # Create a 2D array to store the count
    # of palindromic subsequence
    cps = [[0 for i in range(N + 2)]for j in range(N + 2)]
 
    # palindromic subsequence of length 1
    for i in range(N):
        cps[i][i] = 1
 
    # check subsequence of length L
    # is palindrome or not
    for L in range(2, N + 1):
 
        for i in range(N):
            k = L + i - 1
            if (k < N):
                if (str[i] == str[k]):
                    cps[i][k] = (cps[i][k - 1] +
                                 cps[i + 1][k] + 1)
                else:
                    cps[i][k] = (cps[i][k - 1] +
                                 cps[i + 1][k] -
                                 cps[i + 1][k - 1])
 
    # return total palindromic subsequence
    return cps[0][N - 1]
 
 
# Driver program
str = "abcb"
print("Total palindromic subsequence are : ", countPS(str))
 
 
# This code is contributed by Anant Agarwal.

C#

// C# code to Count Palindromic Subsequence
// Subsequence in a given String
using System;
 
class GFG {
 
    // Function return the total
    // palindromic subsequence
    static int countPS(string str)
    {
        int N = str.Length;
 
        // create a 2D array to store the
        // count of palindromic subsequence
        int[, ] cps = new int[N + 1, N + 1];
 
        // palindromic subsequence
        // of length 1
        for (int i = 0; i < N; i++)
            cps[i, i] = 1;
 
        // check subsequence of length
        // L is palindrome or not
        for (int L = 2; L <= N; L++) {
            for (int i = 0; i <= N-L; i++) {
                int k = L + i - 1;
                if (k < N) {
                    if (str[i] == str[k])
                        cps[i, k] = cps[i, k - 1]
                                    + cps[i + 1, k] + 1;
                    else
                        cps[i, k] = cps[i, k - 1]
                                    + cps[i + 1, k]
                                    - cps[i + 1, k - 1];
                }
            }
        }
 
        // return total palindromic
        // subsequence
        return cps[0, N - 1];
    }
 
    // Driver Code
    public static void Main()
    {
        string str = "abcb";
        Console.Write("Total palindromic "
                      + "subsequence are : "
                      + countPS(str));
    }
}
 
// This code is contributed by nitin mittal.

PHP

<?php
// Counts Palindromic Subsequence in
// a given String
 
// Function return the total
// palindromic subsequence
function countPS($str)
{
    $N = strlen($str);
 
    // create a 2D array to store the
    // count of palindromic subsequence
    $cps = array_fill(0, $N + 1,
           array_fill(0, $N + 1, NULL));
 
    // palindromic subsequence of length 1
    for ($i = 0; $i < $N; $i++)
        $cps[$i][$i] = 1;
 
    // check subsequence of length L
    // is palindrome or not
    for ($L = 2; $L <= $N; $L++)
    {
        for ($i = 0; $i <= $N-$L; $i++)
        {
            $k = $L + $i - 1;
            if ($str[$i] == $str[$k])
                $cps[$i][$k] = $cps[$i][$k - 1] +
                               $cps[$i + 1][$k] + 1;
            else
                $cps[$i][$k] = $cps[$i][$k - 1] +
                               $cps[$i + 1][$k] -
                               $cps[$i + 1][$k - 1];
        }
    }
 
    // return total palindromic subsequence
    return $cps[0][$N - 1];
}
 
// Driver Code
$str = "abcb";
echo "Total palindromic subsequence are : " .
                        countPS($str) . "\n";
 
// This code is contributed by ita_c
?>

Javascript

<script>
 
// Javascript code to Count Palindromic Subsequence
// in a given String
     
    // Function return the total palindromic
    // subsequence
    function countPS(str)
    {
        let N = str.length;
  
        // create a 2D array to store the count
        // of palindromic subsequence
        let cps = new Array(N);
        for(let i=0;i<N;i++)
        {
            cps[i]=new Array(N);
            for(let j=0;j<N;j++)
            {
                cps[i][j]=0;
            }
        }
  
        // palindromic subsequence of length 1
        for (let i = 0; i < N; i++)
            cps[i][i] = 1;
  
        // check subsequence of length L is
        // palindrome or not
        for (let L = 2; L <= N; L++) {
            for (let i = 0; i <= N-L; i++) {
                let k = L + i - 1;
              if (str[i] == str[k]) {
                cps[i][k] = cps[i][k - 1]
                                    + cps[i + 1][k] + 1;
              }else{
                cps[i][k] = cps[i][k - 1]
                                    + cps[i + 1][k]
                                    - cps[i + 1][k - 1];
              }
            }
        }
  
        // return total palindromic subsequence
        return cps[0][N - 1];
    }
     
    // Driver program
    let str = "abcb";
    document.write("Total palindromic "
                           + "subsequence are : "
                           + countPS(str));
     
    // This code is contributed by avanitrachhadiya2155
     
</script>

Producción: 

Total palindromic subsequence are : 6

Complejidad de Tiempo: O(N 2 ), Espacio Auxiliar: O(N 2 )

Otro enfoque: (usando la recursividad)
 

C++

// C++ program to counts Palindromic Subsequence
// in a given String using recursion
#include <bits/stdc++.h>
using namespace std;
 
int n, dp[1000][1000];
string str = "abcb";
 
// Function return the total
// palindromic subsequence
int countPS(int i, int j)
{
 
    if (i > j)
        return 0;
 
    if (dp[i][j] != -1)
        return dp[i][j];
 
    if (i == j)
        return dp[i][j] = 1;
 
    else if (str[i] == str[j])
        return dp[i][j]
               = countPS(i + 1, j) +
                countPS(i, j - 1) + 1;
 
    else
        return dp[i][j] = countPS(i + 1, j) +
                          countPS(i, j - 1) -
                          countPS(i + 1, j - 1);
}
 
// Driver code
int main()
{
    memset(dp, -1, sizeof(dp));
    n = str.size();
    cout << "Total palindromic subsequence are : "
         << countPS(0, n - 1) << endl;
    return 0;
}
// this code is contributed by Kushdeep Mittal

Java

// Java program to counts Palindromic Subsequence
// in a given String using recursion
 
class GFG {
    static int n;
    static int[][] dp = new int[1000][1000];
 
    static String str = "abcb";
 
    // Function return the total
    // palindromic subsequence
    static int countPS(int i, int j)
    {
 
        if (i > j)
            return 0;
 
        if (dp[i][j] != -1)
            return dp[i][j];
     
        if (i == j)
            return dp[i][j] = 1;
 
        else if (str.charAt(i) == str.charAt(j))
            return dp[i][j]
                = countPS(i + 1, j) +
                    countPS(i, j - 1) + 1;
 
        else
            return dp[i][j] = countPS(i + 1, j) +
                              countPS(i, j - 1) -
                              countPS(i + 1, j - 1);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        for (int i = 0; i < 1000; i++)
            for (int j = 0; j < 1000; j++)
                dp[i][j] = -1;
 
        n = str.length();
        System.out.println("Total palindromic subsequence"
                           + "are : " + countPS(0, n - 1));
    }
}
 
// This code is contributed by Ryuga

Python 3

# Python 3 program to counts Palindromic
# Subsequence in a given String using recursion
 
str = "abcb"
 
# Function return the total
# palindromic subsequence
 
 
def countPS(i, j):
 
    if(i > j):
        return 0
 
    if(dp[i][j] != -1):
        return dp[i][j]
 
    if(i == j):
        dp[i][j] = 1
        return dp[i][j]
 
    else if (str[i] == str[j]):
        dp[i][j] = (countPS(i + 1, j) +
                    countPS(i, j - 1) + 1)
        return dp[i][j]
    else:
        dp[i][j] = (countPS(i + 1, j) +
                    countPS(i, j - 1) -
                    countPS(i + 1, j - 1))
        return dp[i][j]
 
 
# Driver code
if __name__ == "__main__":
 
    dp = [[-1 for x in range(1000)]
          for y in range(1000)]
 
    n = len(str)
    print("Total palindromic subsequence are :",
          countPS(0, n - 1))
 
# This code is contributed by ita_c

C#

// C# program to counts Palindromic Subsequence
// in a given String using recursion
using System;
 
class GFG {
    static int n;
    static int[, ] dp = new int[1000, 1000];
 
    static string str = "abcb";
 
    // Function return the total
    // palindromic subsequence
    static int countPS(int i, int j)
    {
 
        if (i > j)
            return 0;
 
        if (dp[i, j] != -1)
            return dp[i, j];
 
        if (i == j)
            return dp[i, j] = 1;
 
        else if (str[i] == str[j])
            return dp[i, j]
                = countPS(i + 1, j) +
                countPS(i, j - 1) + 1;
 
        else
            return dp[i, j] = countPS(i + 1, j)
                              + countPS(i, j - 1)
                              - countPS(i + 1, j - 1);
    }
 
    // Driver code
    static void Main()
    {
        for (int i = 0; i < 1000; i++)
            for (int j = 0; j < 1000; j++)
                dp[i, j] = -1;
 
        n = str.Length;
        Console.Write("Total palindromic subsequence"
                      + "are : " + countPS(0, n - 1));
    }
}
 
// This code is contributed by DrRoot_

PHP

<?php
// PHP program to counts Palindromic Subsequence
// in a given String using recursion
$dp = array_fill(0, 100,
      array_fill(0, 1000, -1));
 
$str = "abcb";
$n = strlen($str);
 
// Function return the total
// palindromic subsequence
function countPS($i, $j)
{
    global $str, $dp, $n;
     
    if($i > $j)
        return 0;
     
    if($dp[$i][$j] != -1)
        return $dp[$i][$j];
     
    if($i == $j)
        return $dp[$i][$j] = 1;
     
    else if ($str[$i] == $str[$j])
        return $dp[$i][$j] = countPS($i + 1, $j) +
                             countPS($i, $j - 1) + 1;
     
    else
        return $dp[$i][$j] = countPS($i + 1, $j) +
                             countPS($i, $j - 1) -
                             countPS($i + 1, $j - 1);
}
 
// Driver code
echo "Total palindromic subsequence are : " .
                          countPS(0, $n - 1);
         
// This code is contributed by mits
?>

Javascript

<script>
// Javascript program to counts Palindromic Subsequence
// in a given String using recursion
     
    let n;
    let dp=new Array(1000);
    for(let i=0;i<1000;i++)
    {
        dp[i]=new Array(1000);
        for(let j=0;j<1000;j++)
        {
            dp[i][j]=-1;
        }
    }
     
     
    let str = "abcb";
  
    // Function return the total
    // palindromic subsequence
    function countPS(i,j)
    {
        if (i > j)
            return 0;
  
        if (dp[i][j] != -1)
            return dp[i][j];
      
        if (i == j)
            return dp[i][j] = 1;
  
        else if (str[i] == str[j])
            return dp[i][j]
                = countPS(i + 1, j) +
                    countPS(i, j - 1) + 1;
  
        else
            return dp[i][j] = countPS(i + 1, j) +
                              countPS(i, j - 1) -
                              countPS(i + 1, j - 1);
    }
     
    // Driver code
     n = str.length;
     document.write("Total palindromic subsequence"
                           + "are : " + countPS(0, n - 1));
     
    // This code is contributed by rag2127
     
</script>

Producción: 

Total palindromic subsequence are : 6

Complejidad de Tiempo: O(N 2 ), Espacio Auxiliar: O(N 2 )

Este artículo es una contribución de Aarti_Rathi y Nishant_sing. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *