Cuente formas de dividir una string en dos subconjuntos que son inversos entre sí

Dada una string S que consta de N caracteres, la tarea es encontrar el número de formas de dividir la string en dos subconjuntos de modo que el primer subconjunto sea el reverso del segundo subconjunto.

Ejemplos:

Entrada: S = “cabaacba”
Salida: 4
Explicación:
A continuación se muestran las formas de particionar la string cumpliendo las condiciones dadas:

1. Tome los caracteres en los índices {0, 4, 6, 7} como el primer subconjunto y los caracteres restantes como el segundo subconjunto. Luego las cuerdas formadas son “caba” y “abac” y la segunda cuerda es la inversa de la primera cuerda.
2. Tome los caracteres en los índices {0, 3, 6, 7} como el primer subconjunto y los caracteres restantes como el segundo subconjunto. Luego las cuerdas formadas son “caba” y “abac” y la segunda cuerda es la inversa de la primera cuerda.
3. Tome los caracteres en los índices {1, 2, 3, 5} como primer subconjunto y los caracteres restantes como segundo subconjunto. Entonces las cuerdas formadas son “abac” y “caba” y la segunda cuerda es el reverso de la primera cuerda.
4. Tome los caracteres en los índices {1, 2, 4, 5} como primer subconjunto y los caracteres restantes como segundo subconjunto. Luego las cuerdas formadas son “abac” y “caba” y la segunda cuerda es la inversa de la primera cuerda.

Por lo tanto, el número de formas de dividir es 4.

Entrada: N = 11, S = “mippiisssisssiipsspiim”
Salida: 504

Enfoque: el problema dado se puede resolver utilizando el concepto de máscara de bits para generar todas las formas posibles de dividir la string y verificar si existe tal división de la string que sea inversa entre sí. Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos ans como 0 para almacenar el número total de formas de dividir la string.
• Iterar sobre el rango [0, 2 ^N ] usando una máscara variable y realizar los siguientes pasos:
  • Inicialice dos strings, digamos X e Y , para almacenar los caracteres del primer subconjunto y el segundo subconjunto.
  • Iterar sobre el rango [0, N] y si el i ^-ésimo bit está configurado en la máscara de enteros , agregue el carácter S[i ] a X. De lo contrario, agregue el carácter S[i] a Y .
  • Invierta la string Y y luego verifique si la primera string X es igual a la segunda string Y , luego incremente ans en 1 .
• Después de completar los pasos anteriores, imprima el valor de ans como el número total de formas.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the total number
// of ways to partitiaon the string into
// two subset satisfying the conditions
int countWays(string S, int N)
{
    // Stores the resultant number of
    // ways of splitting
    int ans = 0;
 
    // Iterate over the range [0, 2^N]
    for (int mask = 0;
         mask < (1 << N); mask++) {
 
        string X, Y;
 
        // Traverse the string S
        for (int i = 0; i < N; i++) {
 
            // If ith bit is set, then
            // append the character
            // S[i] to X
            if (mask >> i & 1) {
                X += S[i];
            }
 
            // Otherwise, append the
            // character S[i] to Y
            else {
                Y += S[i];
            }
        }
 
        // Reverse the second string
        reverse(Y.begin(), Y.end());
 
        // If X is equal to Y
        if (X == Y) {
            ans++;
        }
    }
 
    // Return the total number of ways
    return ans;
}
 
// Driver Code
int main()
{
    string S = "mippiisssisssiipsspiim";
    int N = S.length();
    cout << countWays(S, N);
 
    return 0;
}

// Java program for the above approach
import java.lang.*;
import java.io.*;
import java.util.*;
 
class GFG {
         
    // Function to find the total number
    // of ways to partitiaon the String into
    // two subset satisfying the conditions
    static int countWays(String S, int N)
    {
        // Stores the resultant number of
        // ways of splitting
        int ans = 0;
     
        // Iterate over the range [0, 2^N]
        for (int mask = 0;
             mask < (1 << N); mask++) {
     
            String X="" , Y="";
     
            // Traverse the String S
            for (int i = 0; i < N; i++) {
     
                // If ith bit is set, then
                // append the character
                // S[i] to X
                if ((mask >> i & 1) == 1) {
                    X += S.charAt(i);
                }
     
                // Otherwise, append the
                // character S[i] to Y
                else {
                    Y += S.charAt(i);
                }
            }
     
            // Reverse the second String
            Y = new StringBuilder(Y).reverse().toString();
            // If X is equal to Y
            if (X.equals(Y)) {
                ans++;
            }
        }
     
        // Return the total number of ways
        return ans;
    }
     
    // Driver Code
    public static void main (String[] args)
    {
        String S = "mippiisssisssiipsspiim";
        int N = S.length();
        System.out.println(countWays(S, N));
    }
}
 
// This code is contributed by shubhamsingh10

# Python3 program for the above approach
 
# Function to find the total number
# of ways to partitiaon the string into
# two subset satisfying the conditions
def countWays(S, N):
     
    # Stores the resultant number of
    # ways of splitting
    ans = 0
 
    # Iterate over the range [0, 2^N]
    for mask in range((1 << N)):
        X, Y = "",""
 
        # Traverse the string S
        for i in range(N):
             
            # If ith bit is set, then
            # append the character
            # S[i] to X
            if (mask >> i & 1):
                X += S[i]
                 
            # Otherwise, append the
            # character S[i] to Y
            else:
                Y += S[i]
                 
        # Reverse the second string
        Y = Y[::-1]
         
        # If X is equal to Y
        if (X == Y):
            ans += 1
             
    # Return the total number of ways
    return ans
 
# Driver Code
if __name__ == '__main__':
     
    S = "mippiisssisssiipsspiim"
    N = len(S)
     
    print(countWays(S, N))
 
# This code is contributed by mohit kumar 29

<script>
 
// JavaScript program for the above approach
 
// Function to find the total number
// of ways to partitiaon the string into
// two subset satisfying the conditions
function countWays(S, N){
     
    // Stores the resultant number of
    // ways of splitting
    let ans = 0
 
    // Iterate over the range [0, 2^N]
    for(let mask=0;mask<(1 << N);mask++){
        let X = ""
        let Y = ""
 
        // Traverse the string S
        for(let i=0;i<N;i++){
             
            // If ith bit is set, then
            // append the character
            // S[i] to X
            if (mask >> i & 1)
                X += S[i]
                 
            // Otherwise, append the
            // character S[i] to Y
            else
                Y += S[i]
        }
                 
        // Reverse the second string
        Y = Y.split("").reverse().join("")
         
        // If X is equal to Y
        if (X == Y)
            ans += 1
    }
             
    // Return the total number of ways
    return ans
}
 
// Driver Code
     
let S = "mippiisssisssiipsspiim"
let N = S.length
     
document.write(countWays(S, N))
 
// This code is contributed by shinjanpatra
 
</script>

504

Complejidad temporal: O(N*2 ^N )
Espacio auxiliar: O(N)