Problema
Haz la lista de todas las permutaciones de los caracteres de s en orden lexicográfico (el orden del diccionario). Para "abc" la lista es abc, acb, bac, bca, cab, cba. Devuelve la entrada número k, contando desde 1. Generar la lista completa es demasiado lento con 12 caracteres (479,001,600 permutaciones): cada bloque de permutaciones que empiezan por el mismo carácter tiene (longitud − 1)! elementos, así que puedes elegir los caracteres de uno en uno.
Implementa lexicographic_permutation(s, k).
Entrada
s: caracteres distintos en cualquier orden.
k: la posición en la lista ordenada, contando desde 1.
Salida
Devuelve la k-ésima permutación como cadena. Los caracteres se comparan por su código, así que las cifras van antes que las mayúsculas, y estas antes que las minúsculas.
Restricciones
1 ≤ s.length ≤ 12; todos los caracteres de s son distintos; 1 ≤ k ≤ s.length!
Ejemplos
Entrada:
s = "abc"
k = 4
Salida esperada:
expected = "bca"
Entrada:
std::string s = "abc";
long long k = 4;
Salida esperada:
std::string expected = "bca";
Entrada:
string s = "abc";
long k = 4;
Salida esperada:
string expected = "bca";
Explicación
La lista es abc, acb, bac, bca, cab, cba, y la cuarta es "bca".
Entrada:
s = "312"
k = 1
Salida esperada:
expected = "123"
Entrada:
std::string s = "312";
long long k = 1;
Salida esperada:
std::string expected = "123";
Entrada:
string s = "312";
long k = 1;
Salida esperada:
string expected = "123";
Explicación
La primera permutación son los caracteres ordenados: "123".
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Primero ordena los caracteres.
Pista 2
Cada elección del primer carácter abarca (longitud − 1)! permutaciones, así que al dividir k − 1 entre ese número sabes cuál elegir.
Pista 3
Quita el carácter elegido, quédate con el resto de la división y repite con los caracteres restantes.
Complejidad esperada
tiempo O(n²), espacio extra O(n)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.