Recuento de permutaciones distintas de longitud N que no tienen caracteres adyacentes similares

Dado un número entero N, la tarea es calcular el número total de permutaciones distintas de longitud N , que consisten solo en las letras ‘a’, ‘b’ y ‘c’, con repeticiones permitidas, de modo que no haya dos caracteres adyacentes iguales. .

Entrada: N = 3 
Salida: 12 
Explicación: 
Las permutaciones posibles que satisfacen las condiciones requeridas son {aba, abc, aca, acb, bac, bab, bca, bcb, cac, cab, cba, cbc}
Entrada: N = 5 
Salida: 48

Enfoque: 
Es necesario hacer las siguientes observaciones para resolver el problema dado: 
 

1. Fijemos la primera letra como ‘a’ .
2. Ahora, la ^segunda letra puede ser ‘b’ o ‘c’ , lo que deja 2 formas de completar la segunda letra.
3. Del mismo modo, la tercera letra también se puede completar de dos maneras. Si el carácter en la ^segunda posición es ‘b’, el tercer carácter puede ser ‘a’ o ‘c’. Si el carácter en la ^segunda posición es ‘c’, el tercer carácter puede ser ‘a’ o ‘b’.
4. Del mismo modo, para todas las posiciones restantes, siempre habrá dos posibilidades dependiendo del personaje en la posición anterior. Por lo tanto, el número total de permutaciones posibles si ‘a’ ocupa la primera posición es 1*2*2*2…*2 = 1 * 2 ^{N – 1} .
5. Por lo tanto, el número total de permutaciones, considerando que el primer carácter también puede ser ‘b’ o ‘c’, es 3 * 2 ^{N – 1} .

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 print the number of
// permutations possible
int countofPermutations(int N)
{
    return int(3 * pow(2, N - 1));
}
 
// Driver Code
int main()
{
    int N = 5;
    cout << countofPermutations(N);
    return 0;
}

// Java program to implement
// the above approach
class GFG{
 
// Function to print the number of
// permutations possible
static int countofPermutations(int N)
{
    return (int)(3 * Math.pow(2, N - 1));
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 5;
    System.out.print(countofPermutations(N));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program to implement
# the above approach
 
# Function to print the number of
# permutations possible
def countofPermutations(N):
     
    return int((3 * pow(2, N - 1)));
 
# Driver Code
if __name__ == '__main__':
     
    N = 5;
    print(countofPermutations(N));
 
# This code is contributed by amal kumar choubey

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to print the number of
// permutations possible
static int countofPermutations(int N)
{
    return (int)(3 * Math.Pow(2, N - 1));
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 5;
     
    Console.Write(countofPermutations(N));
}
}
 
// This code is contributed by Amit Katiyar

<script>
 
// Javascript Program to implement
// the above approach
 
// Function to print the number of
// permutations possible
function countofPermutations(N)
{
    return parseInt(3 * Math.pow(2, N - 1));
}
 
// Driver Code
var N = 5;
document.write( countofPermutations(N));
 
</script>

48

Complejidad temporal: O(logN) 
Espacio auxiliar: O(1)