समस्या
s के characters की हर संभव व्यवस्था (क्रमचय) को शब्दकोश क्रम में लिखिए। "abc" के लिए सूची है abc, acb, bac, bca, cab, cba। इसमें से k-वीं प्रविष्टि लौटाइए, 1 से गिनकर। 12 characters के लिए पूरी सूची बनाना बहुत धीमा है (479,001,600 व्यवस्थाएँ): एक ही character से शुरू होने वाली व्यवस्थाओं के हर खंड में (length − 1)! प्रविष्टियाँ होती हैं, इसलिए आप एक-एक करके characters चुन सकते हैं।
lexicographic_permutation(s, k) लिखिए।
इनपुट
s: किसी भी क्रम में दिए गए अलग-अलग characters।
k: sort की गई सूची में स्थान, 1 से गिनकर।
आउटपुट
k-वीं व्यवस्था को string के रूप में लौटाइए। characters की तुलना उनके character codes से होती है, इसलिए अंक uppercase अक्षरों से पहले आते हैं, और uppercase अक्षर lowercase अक्षरों से पहले।
सीमाएँ
1 ≤ s.length ≤ 12; s के सभी characters अलग-अलग हैं; 1 ≤ k ≤ s.length!
उदाहरण
इनपुट:
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";
व्याख्या
सूची है abc, acb, bac, bca, cab, cba, और इसमें चौथी व्यवस्था "bca" है।
इनपुट:
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";
व्याख्या
पहली व्यवस्था में characters sort किए हुए क्रम में होते हैं: "123"।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
पहले characters को sort कीजिए।
संकेत 2
पहले character का हर चुनाव (length − 1)! क्रमचयों को कवर करता है, इसलिए k − 1 को इस संख्या से भाग देने पर वह character मिल जाता है।
संकेत 3
चुने गए character को हटाइए, शेषफल रखिए, और बाकी characters के साथ यही दोहराइए।
अपेक्षित जटिलता
समय O(n²), अतिरिक्त स्थान O(n)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।