Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Lexicographic Permutation

Find the k-th arrangement of some distinct characters in dictionary order.

Das lernst du

  • Skip whole blocks of permutations at once
  • Convert a rank to a permutation
  • Work with 0-based and 1-based positions

Problem

Übersetzung anzeigen

List every arrangement of the characters of s in dictionary order. For "abc" the list is abc, acb, bac, bca, cab, cba. Return the k-th entry, counting from 1. Generating the whole list is too slow for 12 characters (479,001,600 arrangements): each block of arrangements that starts with the same character has (length − 1)! entries, so you can pick one character at a time.

Implement lexicographic_permutation(s, k).

Input

s: Distinct characters in any order.

k: The position in the sorted list, counting from 1.

Output

Return the k-th arrangement as a string. Characters are compared by their character codes, so digits come before uppercase letters, which come before lowercase letters.

Einschränkungen

1 ≤ s.length ≤ 12; all characters of s are distinct; 1 ≤ k ≤ s.length!

Beispiele

Beispiel 1
Eingabe:
s = "abc"
k = 4

Erwartete Ausgabe:
expected = "bca"
Eingabe:
std::string s = "abc";
long long k = 4;

Erwartete Ausgabe:
std::string expected = "bca";
Eingabe:
string s = "abc";
long k = 4;

Erwartete Ausgabe:
string expected = "bca";

Erläuterung

The list is abc, acb, bac, bca, cab, cba, and the fourth is "bca".

Beispiel 2
Eingabe:
s = "312"
k = 1

Erwartete Ausgabe:
expected = "123"
Eingabe:
std::string s = "312";
long long k = 1;

Erwartete Ausgabe:
std::string expected = "123";
Eingabe:
string s = "312";
long k = 1;

Erwartete Ausgabe:
string expected = "123";

Erläuterung

The first arrangement is the characters in sorted order: "123".

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Sort the characters first.

Hinweis 2

Each choice of first character covers (length − 1)! permutations, so dividing k − 1 by that number picks it.

Hinweis 3

Remove the chosen character, keep the remainder, and repeat with the rest.

Erwartete Komplexität

O(n²) time, O(n) extra space

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.