मध्यम 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

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 के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

अभी कोई पास हुआ समाधान नहीं है। इसे हल करें और पहला स्थान पाएँ।

दूसरों से सीखें

समुदाय समाधान

अभी तक कोई प्रकाशित समाधान नहीं। पहला साझा करने के लिए इस चुनौती को हल करें।