मान लीजिए कि हमारे पास एक स्ट्रिंग है। हम इसे हैप्पी स्ट्रिंग कहेंगे जब इसमें केवल ['a', 'b', 'c'] अक्षर, और s[i] !=s[i + 1] 1 से लेकर लंबाई तक के सभी मानों के लिए हों। s - 1 (यहां स्ट्रिंग 1-अनुक्रमित है)।
इसलिए, यदि हमारे पास दो पूर्णांक n और k हैं, तो लेक्सिकोग्राफिक क्रम में क्रमबद्ध n लंबाई के सभी खुश तारों की एक सूची पर विचार करें। हमें इस सूची की kth स्ट्रिंग ढूंढनी होगी या n लंबाई के k हैप्पी स्ट्रिंग्स से कम होने पर एक खाली स्ट्रिंग लौटानी होगी
इसलिए, यदि इनपुट n =3 और k =9 जैसा है, तो आउटपुट "कैब" होगा, 12 अलग-अलग खुश तार हैं, ये हैं ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"], नौवां "कैब" है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक सरणी रिट परिभाषित करें
-
एक फ़ंक्शन हल करें () को परिभाषित करें, इसमें s लगेगा, l इसे 1 से प्रारंभ करें,
-
यदि l, x के समान है, तो −
-
रिट के अंत में s डालें
-
वापसी
-
-
इनिशियलाइज़ करने के लिए मैं :=0, जब i <3, अपडेट (i 1 से बढ़ाएँ), करें -
-
यदि s का अंतिम अवयव c[i] के बराबर नहीं है, तो -
-
हल करें (एस + सी [i], एल + 1)
-
-
-
मुख्य विधि से, निम्न कार्य करें -
-
एक्स:=एन
-
यदि n, 0 के समान है, तो -
-
खाली स्ट्रिंग लौटाएं
-
-
हल करें ("ए")
-
हल करें ("बी")
-
हल करें ("सी")
-
सरणी को क्रमबद्ध करें रिट
-
वापसी (यदि k> रिट का आकार, फिर रिक्त स्ट्रिंग, अन्यथा ret[k - 1])
उदाहरण
आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h>
using namespace std;
struct Cmp{
bool operator()(string& a, string& b) {
return !(a < b);
}
};
char c[3] = {'a', 'b', 'c'};
class Solution {
public:
vector<string> ret;
int x;
void solve(string s, int l = 1){
if (l == x) {
ret.push_back(s);
return;
}
for (int i = 0; i < 3; i++) {
if (s.back() != c[i]) {
solve(s + c[i], l + 1);
}
}
}
string getHappyString(int n, int k){
x = n;
if (n == 0)
return "";
solve("a");
solve("b");
solve("c");
sort(ret.begin(), ret.end());
return k > ret.size() ? "" : ret[k - 1];
}
};
main(){
Solution ob;
cout << (ob.getHappyString(3,9));
} इनपुट
3,9
आउटपुट
cab
