मान लीजिए हमारे पास एक स्ट्रिंग है। हम उसे हैप्पी स्ट्रिंग कहेंगे जब वह केवल ['a', 'b', 'c'] अक्षरों से बनी हो, और सभी i के लिए 1 से s की लंबाई - 1 तक s[i] != s[i + 1] हो (यहाँ स्ट्रिंग 1-इंडेक्स्ड है)।
इसलिए, यदि हमारे पास n और k जैसे दो इंटीजर हैं, तो लंबाई n के सभी हैप्पी स्ट्रिंग्स की सूची पर विचार करें जो लेक्सिकोग्राफिकल क्रम में सॉर्टेड है। हमें इस सूची का k-वां स्ट्रिंग ढूंढना है या खाली स्ट्रिंग लौटानी है यदि लंबाई n के हैप्पी स्ट्रिंग्स k से कम हैं।
इसलिए, यदि इनपुट है n = 3 और k = 9, तो आउटपुट "cab" होगा, 12 अलग-अलग हैप्पी स्ट्रिंग्स हैं, ये हैं ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"], 9वां "cab" है।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
एक ऐरे ret परिभाषित करें
एक फ़ंक्शन solve() परिभाषित करें, जो s, l (1 से इनिशियलाइज़) लेगा,
यदि l, x के समान है, तो -
s को ret के अंत में डालें
लौटें
i := 0 से शुरू करें, जब i < 3, i बढ़ाते हुए, करें -
यदि s का अंतिम एलिमेंट, c[i] के बराबर नहीं है, तो -
solve(s + c[i], l + 1)
मुख्य विधि से, निम्न करें -
x := n
यदि n, 0 के समान है, तो -
खाली स्ट्रिंग लौटाएं
solve("a")
solve("b")
solve("c")
ret ऐरे को सॉर्ट करें
लौटाएं (यदि k > ret का आकार, तो खाली स्ट्रिंग, अन्यथा 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
