K-ésima string lexicográfica de longitud dada

Dados dos números enteros N y K , la tarea es encontrar lexicográficamente la K ^-ésima string de longitud N. Si el número de strings posibles de longitud N es menor que K , imprima -1 .
Ejemplos: 
 

Entrada: N = 3, K = 10 
Salida: “aaj” 
Explicación: La décima string en el orden lexicográfico a partir de “aaa” es “aaj”.
Entrada: N = 2, K = 1000 
Salida: -1 
Explicación: Son posibles un total de 26*26 = 676 strings de longitud 2. Entonces la salida será -1.

Acercarse: 
 

• Supongamos una string de longitud N como un número entero de base 26.

• Por ejemplo, si N = 3, la primera string será s = “aaa” cuya representación en base 26 en número entero será 0 0 0 , la segunda string será s = “aab” y la representación en base 26 será 0 0 1 y pronto. Por lo tanto, cada dígito puede tener un valor dentro de [0, 25] .

• Comenzando desde el último dígito, necesitamos cambiarlo a todos los valores posibles seguido del penúltimo dígito y así sucesivamente.

• Entonces, el problema simplificado es encontrar la representación de un número decimal K en un número base 26. Puede leer esta publicación para tener una idea clara de cómo hacer esto.

• Después de encontrar la respuesta en forma de un número entero de base 26, convertiremos cada dígito en su carácter equivalente, donde 0 es ‘a’ , 1 es ‘b’ , …. 24 es ‘y’ , 25 es ‘z’ .

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

// C++ program to find the K-th
// lexicographical string of length N
#include <bits/stdc++.h>
using namespace std;
 
string find_kth_String_of_n(int n, int k)
{
     
    // Initialize the array to store
    // the base 26 representation of 
    // K with all zeroes, that is, 
    // the initial String consists
    // of N a's
    int d[n] = {0};
 
    // Start filling all the
    // N slots for the base 26
    // representation of K
    for(int i = n - 1; i > -1; i--)
    {
         
       // Store the remainder
       d[i] = k % 26;
        
       // Reduce K
       k /= 26;
    }
     
    // If K is greater than the
    // possible number of strings
    // that can be represented by
    // a string of length N
    if (k > 0)
        return "-1";
 
    string s = "";
     
    // Store the Kth lexicographical
    // string
    for(int i = 0; i < n; i++)
       s += (d[i] + ('a'));
 
    return s;
}
 
// Driver Code
int main()
{
    int n = 3;
    int k = 10;
     
    // Reducing k value by 1 because
    // our stored value starts from 0
    k -= 1;
     
    cout << find_kth_String_of_n(n, k);
    return 0;
}
 
// This code is contributed by 29AjayKumar

// Java program to find the
// K-th lexicographical String
// of length N
class GFG{
     
static String find_kth_String_of_n(int n, int k)
{
    // Initialize the array to
    // store the base 26
    // representation of K
    // with all zeroes, that is,
    // the initial String consists
    // of N a's
    int[] d = new int[n];
 
    // Start filling all the
    // N slots for the base 26
    // representation of K
    for (int i = n - 1; i > -1; i--)
    {
 
        // Store the remainder
        d[i] = k % 26;
 
        // Reduce K
        k /= 26;
    }
     
    // If K is greater than the
    // possible number of Strings
    // that can be represented by
    // a String of length N
    if (k > 0)
        return "-1";
 
    String s = "";
    // Store the Kth lexicographical
    // String
    for (int i = 0; i < n; i++)
        s += (char)(d[i] + ('a'));
 
    return s;
}
 
public static void main(String[] args)
{
    int n = 3;
    int k = 10;
     
    // Reducing k value by 1 because
    // our stored value starts from 0
    k -= 1;
    System.out.println(find_kth_String_of_n(n, k));
}
}
 
// This code is contributed by PrinciRaj1992

# Python program to find the
# K-th lexicographical string
# of length N
def find_kth_string_of_n(n, k):
    # Initialize the array to
    # store the base 26
    # representation of K
    # with all zeroes, that is,
    # the initial string consists
    # of N a's
    d =[0 for i in range(n)]
 
    # Start filling all the
    # N slots for the base 26
    # representation of K
    for i in range(n - 1, -1, -1):
 
        # Store the remainder
        d[i]= k % 26
 
        # Reduce K
        k//= 26
 
    # If K is greater than the
    # possible number of strings
    # that can be represented by
    # a string of length N
    if k>0:
        return -1
     
     
    s =""
    # Store the Kth lexicographical
    # string
    for i in range(n):
        s+= chr(d[i]+ord('a'))
     
    return s    
n = 3
k = 10
# Reducing k value by 1 because
# our stored value starts from 0
k-= 1
print(find_kth_string_of_n(n, k))

// C# program to find the
// K-th lexicographical String
// of length N
using System;
class GFG{
     
static String find_kth_String_of_n(int n, int k)
{
    // Initialize the array to
    // store the base 26
    // representation of K
    // with all zeroes, that is,
    // the initial String consists
    // of N a's
    int[] d = new int[n];
 
    // Start filling all the
    // N slots for the base 26
    // representation of K
    for (int i = n - 1; i > -1; i--)
    {
 
        // Store the remainder
        d[i] = k % 26;
 
        // Reduce K
        k /= 26;
    }
     
    // If K is greater than the
    // possible number of Strings
    // that can be represented by
    // a String of length N
    if (k > 0)
        return "-1";
 
    string s = "";
     
    // Store the Kth lexicographical
    // String
    for (int i = 0; i < n; i++)
        s += (char)(d[i] + ('a'));
 
    return s;
}
 
// Driver Code
public static void Main()
{
    int n = 3;
    int k = 10;
     
    // Reducing k value by 1 because
    // our stored value starts from 0
    k -= 1;
    Console.Write(find_kth_String_of_n(n, k));
}
}
 
// This code is contributed by Code_Mech

<script>
    // Javascript program to find the
    // K-th lexicographical String
    // of length N
     
    function find_kth_String_of_n(n, k)
    {
        // Initialize the array to
        // store the base 26
        // representation of K
        // with all zeroes, that is,
        // the initial String consists
        // of N a's
        let d = new Array(n);
        d.fill(0);
 
        // Start filling all the
        // N slots for the base 26
        // representation of K
        for (let i = n - 1; i > -1; i--)
        {
 
            // Store the remainder
            d[i] = k % 26;
 
            // Reduce K
            k = parseInt(k / 26, 10);
        }
 
        // If K is greater than the
        // possible number of Strings
        // that can be represented by
        // a String of length N
        if (k > 0)
            return "-1";
 
        let s = "";
 
        // Store the Kth lexicographical
        // String
        for (let i = 0; i < n; i++)
            s += String.fromCharCode(d[i] + ('a').charCodeAt());
 
        return s;
    }
     
    let n = 3;
    let k = 10;
       
    // Reducing k value by 1 because
    // our stored value starts from 0
    k -= 1;
    document.write(find_kth_String_of_n(n, k));
 
// This code is contributed by mukesh07.
</script>

aaj

Complejidad temporal: O(N)
Espacio auxiliar: O(N)