Recuento de formas de vaciar una string determinada eliminando recursivamente todos los duplicados adyacentes

Dada una string S , en un movimiento se permite eliminar dos caracteres iguales adyacentes . Después de la eliminación, se unen ambos extremos de los caracteres eliminados. Calcule el número total de formas de vaciar la string. 

Ejemplo: 

Entrada: S = aabccb
Salida: 3
Explicación:
1. aab cc b -> aa bb -> aa 2. aab cc b -> aa bb -> bb 3. aa bccb -> b cc b -> bb Por lo tanto, hay un total de 3 formas de vaciar la string después de un conjunto válido de movimientos.  

Entrada: S = aabbc
Salida: 0
Explicación: La string tiene una longitud impar, por lo que no es posible vaciar toda la string.

Enfoque: el problema anterior se puede resolver con la ayuda de la programación dinámica. Siga los pasos a continuación para resolver el problema:

• Definamos una tabla dp 2-d dp[i][j] que almacenará la respuesta para el rango [i, j].
• Defina un enfoque recursivo para resolver el problema.
• Para calcular dp[i][j] , recorra todos los índices k entre i y j donde S[i] = S[k] .
• Ahora, para un k individual , la respuesta sería dp[i+1][k-1]*dp[k+1][j]*(Número total de formas de organizar las eliminaciones del rango).
• Para calcular el último término de la ecuación, observe que la eliminación de todo el rango [i+1, k-1] tendrá lugar antes de la eliminación de S[i] y S[k].
• Entonces, las eliminaciones totales en el rango serán (j – i + 1)/2 (ya que se eliminan dos elementos a la vez). De estas eliminaciones hay que elegir (j – k)/2 eliminaciones.
• Así que la fórmula final será 
   

• Utilice la memorización para no volver a calcular los estados de nuevo.
• Verifique los casos base en la función recursiva.
• La respuesta final será dp[0][N-1]

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Define the dp table globally
int dp[505][505], choose[502][502];
 
// Recursive function to calculate the dp
// values for range [L, R]
int calc(int l, int r, string& s)
{
 
    // The range is odd length
    if (abs(r - l) % 2 == 0) {
        return 0;
    }
 
    if (l > r) {
        return dp[l][r] = 1;
    }
 
    // The state is already calculated
    if (dp[l][r] != -1) {
        return dp[l][r];
    }
 
    // If the length is 2
    if ((r - l) == 1) {
        if (s[l] == s[r]) {
            dp[l][r] = 1;
        }
        else {
            dp[l][r] = 0;
        }
        return dp[l][r];
    }
 
    // Total answer for this state
    int ans = 0;
    for (int k = l + 1; k <= r; k += 2) {
 
        // Variable to store the current answer.
        int temp = 1;
 
        // Remove characters s[l] and s[i].
        if (s[l] == s[k]) {
            temp = calc(l + 1, k - 1, s)
                   * calc(k + 1, r, s)
                   * choose[(r - l + 1) / 2]
                           [(r - k) / 2];
            ans += temp;
        }
    }
    return dp[l][r] = ans;
}
 
int waysToClearString(string S)
{
 
    // Initialize all the states of dp to -1
    memset(dp, -1, sizeof(dp));
 
    // Calculate all Combinations
    int n = S.length();
    choose[0][0] = 1;
    for (int i = 1; i <= n / 2; ++i) {
        choose[i][0] = 1;
        for (int j = 1; j <= i; ++j) {
            choose[i][j]
                = (choose[i - 1][j]
                   + choose[i - 1][j - 1]);
        }
    }
    return calc(0, n - 1, S);
}
 
// Driver Code
int main()
{
    string S = "aabccb";
 
    cout << waysToClearString(S);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
class GFG
{
 
// Define the dp table globally
static int [][]dp = new int[505][505];
static int [][]choose = new int[502][502];
 
// Recursive function to calculate the dp
// values for range [L, R]
static int calc(int l, int r, String s)
{
 
    // The range is odd length
            if (Math.abs(r - l) % 2 == 0) {
                return 0;
            }
 
            if (l > r) {
                return dp[l][r] = 1;
            }
 
            // The state is already calculated
            if (dp[l][r] != -1) {
                return dp[l][r];
            }
 
            // If the length is 2
            if ((r - l) == 1) {
                if (s.charAt(l) == s.charAt(r)) {
                    dp[l][r] = 1;
                }
                else {
                    dp[l][r] = 0;
                }
                return dp[l][r];
            }
 
            // Total answer for this state
            int ans = 0;
            for (int k = l + 1; k <= r; k += 2) {
 
                // Variable to store the current answer.
                int temp = 1;
 
                // Remove characters s[l] and s[i].
                if (s.charAt(l) == s.charAt(k)) {
                    temp = calc(l + 1, k - 1, s)
                        * calc(k + 1, r, s)
                        * choose[((r - l + 1) / 2)]
                        [((r - k) / 2)];
                    ans += temp;
                }
            }
            return dp[l][r] = ans;
}
 
static int waysToClearString(String S)
{
 
    // Initialize all the states of dp to -1
    // Initialize all the states of dp to -1
    for(int i=0;i<505;i++){
        for(int j=0;j<505;j++)
            dp[i][j] = -1;
    }
 
            // Calculate all Combinations
            int n = S.length();
            choose[0][0] = 1;
            for (int i = 1; i <= (n / 2); ++i) {
                choose[i][0] = 1;
                for (int j = 1; j <= i; ++j) {
                    choose[i][j]
                        = (choose[i - 1][j]
                            + choose[i - 1][j - 1]);
                }
            }
            return calc(0, n - 1, S);
}
 
// Driver Code
public static void main (String[] args)
{
    String S = "aabccb";
 
    System.out.println(waysToClearString(S));
}
}
 
// This code is contributed by sanjoy_62.

# Python3 implementation for the above approach
import numpy as np
 
# Define the dp table globally
dp = np.zeros((505,505));
choose = np.zeros((502,502));
 
# Recursive function to calculate the dp
# values for range [L, R]
def calc(l, r, s) :
 
    # The range is odd length
    if (abs(r - l) % 2 == 0) :
        return 0;
 
    if (l > r) :
        dp[l][r] = 1;
        return dp[l][r]
 
    # The state is already calculated
    if (dp[l][r] != -1) :
        return dp[l][r];
 
    # If the length is 2
    if ((r - l) == 1) :
        if (s[l] == s[r]) :
            dp[l][r] = 1;
         
        else :
            dp[l][r] = 0;
         
        return dp[l][r];
     
    # Total answer for this state
    ans = 0;
     
    for k in range(l + 1, r + 1, 2) :
 
        # Variable to store the current answer.
        temp = 1;
 
        # Remove characters s[l] and s[i].
        if (s[l] == s[k]) :
            temp = calc(l + 1, k - 1, s) * calc(k + 1, r, s) * choose[(r - l + 1) // 2][(r - k) // 2];
            ans += temp;
         
     
    dp[l][r] = ans;
    return dp[l][r]
 
def waysToClearString(S) :
 
 
    # Initialize all the states of dp to -1
    #memset(dp, -1, sizeof(dp));
     
    for i in range(505):
        for j in range(505) :
            dp[i][j] = -1
 
    # Calculate all Combinations
    n = len(S);
    choose[0][0] = 1;
    for i in range(1, (n // 2) + 1) :
        choose[i][0] = 1;
        for j in range(1, i + 1) :
            choose[i][j]= choose[i - 1][j] + choose[i - 1][j - 1];
     
    return calc(0, n - 1, S);
 
# Driver Code
if __name__ == "__main__" :
 
    S = "aabccb";
 
    print(waysToClearString(S));
 
    # This code is contributed by AnkThon

// C# implementation for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
// Define the dp table globally
static int [,]dp = new int[505,505];
static int [,]choose = new int[502,502];
 
// Recursive function to calculate the dp
// values for range [L, R]
static int calc(int l, int r, string s)
{
 
    // The range is odd length
    if (Math.Abs(r - l) % 2 == 0) {
        return 0;
    }
 
    if (l > r) {
        return dp[l,r] = 1;
    }
 
    // The state is already calculated
    if (dp[l,r] != -1) {
        return dp[l,r];
    }
 
    // If the length is 2
    if ((r - l) == 1) {
        if (s[l] == s[r]) {
            dp[l,r] = 1;
        }
        else {
            dp[l,r] = 0;
        }
        return dp[l,r];
    }
 
    // Total answer for this state
    int ans = 0;
    for (int k = l + 1; k <= r; k += 2) {
 
        // Variable to store the current answer.
        int temp = 1;
 
        // Remove characters s[l] and s[i].
        if (s[l] == s[k]) {
            temp = calc(l + 1, k - 1, s)
                   * calc(k + 1, r, s)
                   * choose[(r - l + 1) / 2,(r - k) / 2];
            ans += temp;
        }
    }
    return dp[l,r] = ans;
}
 
static int waysToClearString(string S)
{
 
    // Initialize all the states of dp to -1
    for(int i=0;i<505;i++){
        for(int j=0;j<505;j++)
            dp[i,j] = -1;
    }
 
    // Calculate all Combinations
    int n = S.Length;
    choose[0,0] = 1;
    for (int i = 1; i <= n / 2; ++i) {
        choose[i,0] = 1;
        for (int j = 1; j <= i; ++j) {
            choose[i,j]
                = (choose[i - 1,j]
                   + choose[i - 1,j - 1]);
        }
    }
    return calc(0, n - 1, S);
}
 
// Driver Code
public static void Main()
{
    string S = "aabccb";
 
    Console.Write(waysToClearString(S));
}
}
 
// This code is contributed by ipg2016107.

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Define the dp table globally
        var dp = new Array(505);
 
        for (var i = 0; i < dp.length; i++) {
            dp[i] = new Array(505).fill(-1);
        }
        var choose = new Array(505);
 
        for (var i = 0; i < choose.length; i++) {
            choose[i] = new Array(505).fill(0);
        }
 
 
        // Recursive function to calculate the dp
        // values for range [L, R]
        function calc(l, r, s) {
 
            // The range is odd length
            if (Math.abs(r - l) % 2 == 0) {
                return 0;
            }
 
            if (l > r) {
                return dp[l][r] = 1;
            }
 
            // The state is already calculated
            if (dp[l][r] != -1) {
                return dp[l][r];
            }
 
            // If the length is 2
            if ((r - l) == 1) {
                if (s[l] == s[r]) {
                    dp[l][r] = 1;
                }
                else {
                    dp[l][r] = 0;
                }
                return dp[l][r];
            }
 
            // Total answer for this state
            let ans = 0;
            for (let k = l + 1; k <= r; k += 2) {
 
                // Variable to store the current answer.
                let temp = 1;
 
                // Remove characters s[l] and s[i].
                if (s[l] == s[k]) {
                    temp = calc(l + 1, k - 1, s)
                        * calc(k + 1, r, s)
                        * choose[Math.floor((r - l + 1) / 2)]
                        [Math.floor((r - k) / 2)];
                    ans += temp;
                }
            }
            return dp[l][r] = ans;
        }
 
        function waysToClearString(S) {
 
            // Initialize all the states of dp to -1
 
 
            // Calculate all Combinations
            let n = S.length;
            choose[0][0] = 1;
            for (let i = 1; i <= Math.floor(n / 2); ++i) {
                choose[i][0] = 1;
                for (let j = 1; j <= i; ++j) {
                    choose[i][j]
                        = (choose[i - 1][j]
                            + choose[i - 1][j - 1]);
                }
            }
            return calc(0, n - 1, S);
        }
 
        // Driver Code
 
        let S = "aabccb";
 
        document.write(waysToClearString(S));
 
// This code is contributed by Potta Lokesh
 
    </script>

3

Complejidad de tiempo: O(N^3)
Espacio auxiliar: O(N^2)