Conteo de strings palindrómicas de tamaño hasta N que consisten en los primeros K alfabetos que ocurren como máximo dos veces

Posted on by Rudeus Greyrat

Dados dos números enteros N y K , la tarea es encontrar el número de strings palindrómicas de tamaño como máximo N que consisten en los primeros K alfabetos en minúsculas de modo que cada carácter en una string no aparezca más de dos veces.

Ejemplos:

Entrada: N = 3, K = 2
Salida: 6
Explicación:
Las strings posibles son:
“a”, “b”, “aa”, “bb”, “aba”, “bab”.

Entrada: N = 4, K = 3
Salida: 18
Explicación:
Las strings posibles son: 
“a”, “b”, “c”, “aa”, “bb”, “cc”, “aba”, “aca” , “bab”, “bcb”, “cac”, “cbc”, “abba”, “acca”, “baab”, “bccb”, “caac”, “cbbc”.

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

  • Intentemos construir un palíndromo de 4 dígitos ( N = 4 ) con solo las primeras 3 letras en inglés ( K = 3 ). Entonces, la idea es crear una string vacía ( _ _ _ _ ) y ahora para sacar un palíndromo de ella, solo se pueden llenar los dos dígitos en uno en su mitad porque los otros dos se decidirían sobre la base de ellos, es decir, si se eligen los 2 primeros lugares para llenar con un carácter de elección, los dos últimos serán iguales a eso, por lo que la string debe ser un palíndromo.
  • Aquí, en este caso, si a se llena en la primera posición y b en la segunda, entonces la única opción que queda para la 3ra y la 4ta es llenarse con b y a respectivamente.
  • Esto significa que, para encontrar el número de strings palindrómicas con longitud 4 ( N = 4 ) con solo las primeras 3 letras ( K = 3 ), cuente todas las combinaciones posibles para los primeros 2 dígitos (= N/2 ), es decir, 3 *2=6 (3 opciones para la primera posición y 2 opciones para la segunda).
  • El caso explicado anteriormente es para una string de longitud par ( N es par ), y para una string de longitud impar ( N es impar ), se pueden llenar N/2 + 1 índices.

Siga los pasos a continuación para resolver el problema dado:

  1. Para encontrar las cuerdas palindrómicas de conteo de longitud como máximo N , luego cuente las cuerdas palindrómicas de cada longitud de 1 a N y luego súmelas.
  2. Para el valor de N como:
    • Si N es par, encuentre todas las combinaciones posibles hasta N/2 porque solo se pueden llenar la mitad de las posiciones.
    • Si N es impar, encuentre todas las combinaciones posibles hasta N/2 +1 y extra + 1 para el elemento del medio.
  3. Súmalos todos juntos e imprime la respuesta en consecuencia.

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function of return the number of
// palindromic strings of length N with
// first K alphabets possible
int lengthNPalindrome(int N, int K)
{
    int half = N / 2;
 
    // If N is odd, half + 1 position
    // can be filled to cope with the
    // extra middle element
    if (N & 1) {
        half += 1;
    }
 
    int ans = 1;
    for (int i = 1; i <= half; i++) {
        ans *= K;
 
        // K is reduced by one, because
        // count of choices for the next
        // position is  reduced by 1 as
        // a element can only once
        K--;
    }
 
    // Return the possible count
    return ans;
}
 
// Function to find the count of palindromic
// string of first K characters according
// to the given criteria
int palindromicStrings(int N, int K)
{
    // If N=1, then only K palindromic
    // strings possible.
    if (N == 1) {
        return K;
    }
 
    // If N=2, the 2*K palindromic strings
    // possible, K for N=1 and K for N=2
    if (N == 2) {
        return 2 * K;
    }
 
    int ans = 0;
 
    // Initialize ans with the count of
    // strings possible till N = 2
    ans += (2 * K);
 
    for (int i = 3; i <= N; i++) {
        ans += lengthNPalindrome(i, K);
    }
 
    // Return the possible count
    return ans;
}
 
// Driver Code
int main()
{
    int N = 4, K = 3;
    cout << palindromicStrings(N, K);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
 
class GFG {
    // Function of return the number of
    // palindromic strings of length N with
    // first K alphabets possible
    static int lengthNPalindrome(int N, int K)
    {
        int half = N / 2;
 
        // If N is odd, half + 1 position
        // can be filled to cope with the
        // extra middle element
        if (N % 2 == 1) {
            half += 1;
        }
 
        int ans = 1;
        for (int i = 1; i <= half; i++) {
            ans *= K;
 
            // K is reduced by one, because
            // count of choices for the next
            // position is  reduced by 1 as
            // a element can only once
            K--;
        }
 
        // Return the possible count
        return ans;
    }
 
    // Function to find the count of palindromic
    // string of first K characters according
    // to the given criteria
    static int palindromicStrings(int N, int K)
    {
        // If N=1, then only K palindromic
        // strings possible.
        if (N == 1) {
            return K;
        }
 
        // If N=2, the 2*K palindromic strings
        // possible, K for N=1 and K for N=2
        if (N == 2) {
            return 2 * K;
        }
 
        int ans = 0;
 
        // Initialize ans with the count of
        // strings possible till N = 2
        ans += (2 * K);
 
        for (int i = 3; i <= N; i++) {
            ans += lengthNPalindrome(i, K);
        }
 
        // Return the possible count
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 4, K = 3;
 
        System.out.println(palindromicStrings(N, K));
    }
}
// This code is contributed by Potta Lokesh

Python3

# Python3 program for the above approach
 
 
# Function of return the number of
# palindromic strings of length N with
# first K alphabets possible
def lengthNPalindrome(N, K) :
     
    half = N // 2;
 
    # If N is odd, half + 1 position
    # can be filled to cope with the
    # extra middle element
    if (N & 1) :
        half += 1;
 
    ans = 1;
    for i in range(1, half + 1) :
        ans *= K;
 
        # K is reduced by one, because
        # count of choices for the next
        # position is  reduced by 1 as
        # a element can only once
        K -= 1;
 
    # Return the possible count
    return ans;
 
# Function to find the count of palindromic
# string of first K characters according
# to the given criteria
def palindromicStrings(N, K) :
 
    # If N=1, then only K palindromic
    # strings possible.
    if (N == 1) :
        return K;
 
    # If N=2, the 2*K palindromic strings
    # possible, K for N=1 and K for N=2
    if (N == 2) :
        return 2 * K;
 
    ans = 0;
 
    # Initialize ans with the count of
    # strings possible till N = 2
    ans += (2 * K);
 
    for i in range(3, N + 1) :
        ans += lengthNPalindrome(i, K);
 
    # Return the possible count
    return ans;
 
# Driver Code
if __name__ == "__main__" :
 
    N = 4; K = 3;
    print(palindromicStrings(N, K));
 
    # This code is contributed by AnkThon

C#

// C# program for the above approach
using System;
 
class GFG
{
   
    // Function of return the number of
    // palindromic strings of length N with
    // first K alphabets possible
    static int lengthNPalindrome(int N, int K)
    {
        int half = N / 2;
 
        // If N is odd, half + 1 position
        // can be filled to cope with the
        // extra middle element
        if (N % 2 == 1) {
            half += 1;
        }
 
        int ans = 1;
        for (int i = 1; i <= half; i++) {
            ans *= K;
 
            // K is reduced by one, because
            // count of choices for the next
            // position is  reduced by 1 as
            // a element can only once
            K--;
        }
 
        // Return the possible count
        return ans;
    }
 
    // Function to find the count of palindromic
    // string of first K characters according
    // to the given criteria
    static int palindromicStrings(int N, int K)
    {
        // If N=1, then only K palindromic
        // strings possible.
        if (N == 1) {
            return K;
        }
 
        // If N=2, the 2*K palindromic strings
        // possible, K for N=1 and K for N=2
        if (N == 2) {
            return 2 * K;
        }
 
        int ans = 0;
 
        // Initialize ans with the count of
        // strings possible till N = 2
        ans += (2 * K);
 
        for (int i = 3; i <= N; i++) {
            ans += lengthNPalindrome(i, K);
        }
 
        // Return the possible count
        return ans;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int N = 4, K = 3;
 
        Console.Write(palindromicStrings(N, K));
    }
}
 
// This code is contributed by shivanisinghss2110

Javascript

<script>
 
// Javascript program for the above approach
 
// Function of return the number of
// palindromic strings of length N with
// first K alphabets possible
function lengthNPalindrome(N,K)
{
    var half = N / 2;
 
    // If N is odd, half + 1 position
    // can be filled to cope with the
    // extra middle element
    if (N & 1) {
        half += 1;
    }
 
    var ans = 1;
    var i;
    for(i = 1; i <= half; i++) {
        ans *= K;
 
        // K is reduced by one, because
        // count of choices for the next
        // position is  reduced by 1 as
        // a element can only once
        K--;
    }
 
    // Return the possible count
    return ans;
}
 
// Function to find the count of palindromic
// string of first K characters according
// to the given criteria
function palindromicStrings(N, K)
{
    // If N=1, then only K palindromic
    // strings possible.
    if (N == 1) {
        return K;
    }
 
    // If N=2, the 2*K palindromic strings
    // possible, K for N=1 and K for N=2
    if (N == 2) {
        return 2 * K;
    }
 
    ans = 0;
 
    // Initialize ans with the count of
    // strings possible till N = 2
    ans += (2 * K);
 
    for (i = 3; i <= N; i++) {
        ans += lengthNPalindrome(i, K);
    }
 
    // Return the possible count
    return ans;
}
 
// Driver Code
    var N = 4, K = 3;
    document.write(palindromicStrings(N, K));
 
// This code is contributed by ipg2016107.
</script>
Producción: 

18

 

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

Publicación traducida automáticamente

Artículo escrito por srrajeshsarkar 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 *