ধরুন আমাদের একটি স্ট্রিং আছে। আমরা এটিকে একটি সুখী স্ট্রিং বলব যখন এটি শুধুমাত্র ['a', 'b', 'c'] অক্ষর এবং s[i]!=s[i + 1] এর 1 থেকে দৈর্ঘ্য পর্যন্ত সমস্ত মানের জন্য থাকে। s - 1 (এখানে স্ট্রিংটি 1-সূচীযুক্ত)।
সুতরাং, যদি আমাদের দুটি পূর্ণসংখ্যা n এবং k থাকে, তাহলে আভিধানিক ক্রম অনুসারে n দৈর্ঘ্যের সমস্ত সুখী স্ট্রিংগুলির একটি তালিকা বিবেচনা করুন। আমাদের এই তালিকার kth স্ট্রিং খুঁজে বের করতে হবে অথবা 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 এর সমান হয়, তাহলে −
-
ret এর শেষে s ঢোকান
-
ফেরত
-
-
আরম্ভ করার জন্য i :=0, যখন i <3, আপডেট করুন (i 1 দ্বারা বাড়ান), −
-
যদি s এর শেষ উপাদানটি c[i] এর সমান না হয়, তাহলে −
-
সমাধান (s + c[i], l + 1)
-
-
-
প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
-
x :=n
-
যদি n 0 এর সমান হয়, তাহলে −
-
খালি স্ট্রিং ফেরত দিন
-
-
সমাধান("a")
-
সমাধান("b")
-
সমাধান("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
