के-वें लेक्सिकोग्राफ़िकल स्ट्रिंग ऑफ़ ऑल हैप्पी स्ट्रिंग्स ऑफ़ लेंथ एन इन C++

मान लीजिए कि हमारे पास एक स्ट्रिंग है। हम इसे हैप्पी स्ट्रिंग कहेंगे जब इसमें केवल ['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