Contar formas de colocar todos los caracteres de dos strings dadas alternativamente

Dadas dos strings, str1 de longitud N y str2 de longitud M de caracteres distintos, la tarea es contar el número de formas de colocar todos los caracteres de str1 y str2 alternativamente.

Nota: |N – M| ≤ 1

Ejemplos:

Entrada: str1 =“ae ”, str2 = “bd ”
Salida: 8
Explicaciones:
Las strings posibles después de los reordenamientos son: {“abed ”, “ebad ”, “adeb ”, “edab”, “bade ”, “beda ”, “ dabe ”, “deba ” }. Por lo tanto, la salida requerida es 8.

Entrada: str1= “aegh” , str2=”rsw”
Salida: 144

Enfoque: El problema se puede resolver con base en las siguientes observaciones:

Si N != M: Considere solo el caso de N > M porque de manera similar, funcionará para el caso de N < M .

Posibles formas de colocar str1[] y str2[] ​​alternativamente

Número total de formas de reorganizar todos los caracteres de str1 = N!
Número total de formas de reorganizar todos los caracteres de str2 = M! .
Por lo tanto, el número total de formas de colocar todos los caracteres de str1 y str2 alternativamente es = N. * M!

Si N == M:

Primero coloque el carácter de str1[] y luego coloque el carácter de str2[]

Primero coloque el carácter de str2[] ​​y luego coloque el carácter de str1[]

Número total de formas de reorganizar todos los caracteres de str1 = N!
Número total de formas de reorganizar todos los caracteres de str2 = M!
Ahora, 
hay dos casos posibles aquí:

• Primero coloque el carácter de str1 y luego coloque el carácter de str2 .
• Primero coloque el carácter de str2 y luego coloque el carácter de str1 .

Por lo tanto, el número total de vías = (2 * N! * M!) . 
 

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

// C++ Program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to get the
// factorial of N
int fact(int n)
{
    int res = 1;
    for (int i = 1; i <= n; i++) {
        res = res * i;
    }
    return res;
}
 
// Function to get the total
// number of  distinct ways
int distinctWays(string str1, string str2)
{
    // Length of str1
    int n = str1.length();
 
    // Length of str2
    int m = str2.length();
 
    // If both strings have equal length
    if (n == m) {
        return 2 * fact(n) * fact(m);
    }
 
    // If both strings do not have
    // equal length
    return fact(n) * fact(m);
}
 
// Driver code
int main()
{
    string str1 = "aegh";
    string str2 = "rsw";
 
    cout << distinctWays(str1, str2);
}

// Java program to implement
// the above approach
import java.io.*;
 
class GFG{
 
// Function to get the
// factorial of N
static int fact(int n)
{
    int res = 1;
    for(int i = 1; i <= n; i++)
    {
        res = res * i;
    }
    return res;
}
 
// Function to get the total
// number of distinct ways
static int distinctWays(String str1,
                        String str2)
{
     
    // Length of str1
    int n = str1.length();
 
    // Length of str2
    int m = str2.length();
 
    // If both strings have equal length
    if (n == m)
    {
        return 2 * fact(n) * fact(m);
    }
 
    // If both strings do not have
    // equal length
    return fact(n) * fact(m);
}
 
// Driver code
public static void main (String[] args)
{
    String str1 = "aegh";
    String str2 = "rsw";
 
    System.out.print(distinctWays(str1, str2));
}
}
 
// This code is contributed by code_hunt

# Python3 program to implement
# the above approach
 
# Function to get the
# factorial of N
def fact(n):
     
    res = 1
    for i in range(1, n + 1):
        res = res * i
     
    return res
 
# Function to get the total
# number of distinct ways
def distinctWays(str1, str2):
     
    # Length of str1
    n = len(str1)
 
    # Length of str2
    m = len(str2)
 
    # If both strings have equal length
    if (n == m):
        return 2 * fact(n) * fact(m)
     
    # If both strings do not have
    # equal length
    return fact(n) * fact(m)
 
# Driver code
str1 = "aegh"
str2 = "rsw"
 
print(distinctWays(str1, str2))
 
# This code is contributed by code_hunt

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to get the
// factorial of N
static int fact(int n)
{
    int res = 1;
    for(int i = 1; i <= n; i++)
    {
        res = res * i;
    }
    return res;
}
 
// Function to get the total
// number of distinct ways
static int distinctWays(string str1,
                        string str2)
{
     
    // Length of str1
    int n = str1.Length;
 
    // Length of str2
    int m = str2.Length;
 
    // If both strings have equal length
    if (n == m)
    {
        return 2 * fact(n) * fact(m);
    }
 
    // If both strings do not have
    // equal length
    return fact(n) * fact(m);
}
 
// Driver code
public static void Main ()
{
    string str1 = "aegh";
    string str2 = "rsw";
 
    Console.Write(distinctWays(str1, str2));
}
}
 
// This code is contributed by code_hunt

<script>
 
// JavaScript program to implement
// the above approach
 
    // Function to get the
    // factorial of N
    function fact(n) {
        var res = 1;
        for (i = 1; i <= n; i++) {
            res = res * i;
        }
        return res;
    }
 
    // Function to get the total
    // number of distinct ways
    function distinctWays( str1,  str2) {
 
        // Length of str1
        var n = str1.length;
 
        // Length of str2
        var m = str2.length;
 
        // If both strings have equal length
        if (n == m) {
            return 2 * fact(n) * fact(m);
        }
 
        // If both strings do not have
        // equal length
        return fact(n) * fact(m);
    }
 
    // Driver code
     
        var str1 = "aegh";
        var str2 = "rsw";
 
        document.write(distinctWays(str1, str2));
 
// This code is contributed by todaysgaurav
 
</script>

144

Complejidad temporal: O(N + M)  
Espacio auxiliar: O(1)