中級 0件解決済み 正答率0%

Lexicographic Permutation

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

このチャレンジで学べること

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

問題

翻訳を表示

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.

制約

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

例

例 1
入力:
s = "abc"
k = 4

期待される出力:
expected = "bca"
入力:
std::string s = "abc";
long long k = 4;

期待される出力:
std::string expected = "bca";
入力:
string s = "abc";
long k = 4;

期待される出力:
string expected = "bca";

解説

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

例 2
入力:
s = "312"
k = 1

期待される出力:
expected = "123"
入力:
std::string s = "312";
long long k = 1;

期待される出力:
std::string expected = "123";
入力:
string s = "312";
long k = 1;

期待される出力:
string expected = "123";

解説

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

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

Sort the characters first.

ヒント 2

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

ヒント 3

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

目安の計算量

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

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。