Problema
Liste todas as permutações dos caracteres de s em ordem lexicográfica (a ordem do dicionário). Para "abc", a lista é abc, acb, bac, bca, cab, cba. Retorne a k-ésima entrada, contando a partir de 1. Gerar a lista inteira é lento demais para 12 caracteres (479 001 600 permutações): cada bloco de permutações que começa com o mesmo caractere tem (tamanho − 1)! entradas, então dá para escolher um caractere de cada vez.
Implemente lexicographic_permutation(s, k).
Entrada
s: caracteres distintos, em qualquer ordem.
k: a posição na lista ordenada, contando a partir de 1.
Saída
Retorne a k-ésima permutação como uma string. Os caracteres são comparados pelos seus códigos, então os dígitos vêm antes das letras maiúsculas, que vêm antes das minúsculas.
Restrições
1 ≤ s.length ≤ 12; todos os caracteres de s são distintos; 1 ≤ k ≤ s.length!
Exemplos
Entrada:
s = "abc"
k = 4
Saída esperada:
expected = "bca"
Entrada:
std::string s = "abc";
long long k = 4;
Saída esperada:
std::string expected = "bca";
Entrada:
string s = "abc";
long k = 4;
Saída esperada:
string expected = "bca";
Explicação
A lista é abc, acb, bac, bca, cab, cba, e a quarta é "bca".
Entrada:
s = "312"
k = 1
Saída esperada:
expected = "123"
Entrada:
std::string s = "312";
long long k = 1;
Saída esperada:
std::string expected = "123";
Entrada:
string s = "312";
long k = 1;
Saída esperada:
string expected = "123";
Explicação
A primeira permutação é a dos caracteres em ordem: "123".
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Ordene os caracteres primeiro.
Dica 2
Cada escolha do primeiro caractere cobre (tamanho − 1)! permutações, então dividir k − 1 por esse número indica qual escolher.
Dica 3
Remova o caractere escolhido, guarde o resto da divisão e repita com os caracteres restantes.
Complexidade esperada
tempo O(n²), espaço extra O(n)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.