একটি স্ট্রিং "হ্যাপি" যদি শুধু 'a','b','c' দিয়ে বানানো থাকে এবং কোনো দুটি সংলগ্ন অক্ষর একই নয়। দৈর্ঘ্য n ওয়ালা সব হ্যাপি স্ট্রিং লেক্সিকোগ্রাফিক্যালি সর্ট করে k-তমটি বের করতে হবে।
ইনপুট: n=3, k=9 → আউটপুট: "cab" (মোট ১২টি হ্যাপি স্ট্রিং, ৯তম "cab")
সমাধানের ধাপগুলো (ব্যাকট্র্যাকিং):
solve(s, len)রিকার্সিভ ফাংশন: শেষ অক্ষর চেক করে 'a','b','c' যোগ করববেস কেস:
len == nহলেretএ যোগ করব"a","b","c" দিয়ে শুরু করব
retসর্ট করেk-1ইনডেক্স রিটার্ন করব (যদিk > sizeহয় তবে খালি স্ট্রিং)
উদাহরণ
নিচের কোডটি দেখুন −
#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];
}
};
int main() {
Solution ob;
cout << (ob.getHappyString(3, 9));
}
ইনপুট
3,9
আউটপুট
cab
