ধরুন একটি স্ট্রিং আছে। সেই স্ট্রিংটিকে খুশি বলা হয় যদি সাবস্ট্রিং হিসাবে 'aa', 'bbb' বা 'ccc' এর মতো কোনও স্ট্রিং না থাকে। যদি আমাদের তিনটি পূর্ণসংখ্যা থাকে যেমন a, b এবং c, তাহলে যেকোনো স্ট্রিং s ফেরত দিন, যা নিম্নলিখিত শর্তগুলি পূরণ করে -
-
s সুখী এবং দীর্ঘতম সম্ভব৷
৷ -
s-এ সর্বাধিক 'a' অক্ষরের সংঘটন রয়েছে, সর্বাধিক b অক্ষরের 'b' এবং সর্বাধিক c অক্ষরের 'c' সংঘটন রয়েছে।
-
s-এ শুধুমাত্র 'a', 'b' এবং 'c' অক্ষর থাকবে।
যদি এমন কোন স্ট্রিং না থাকে, তাহলে একটি খালি স্ট্রিং ফেরত দিন।
সুতরাং, যদি ইনপুট হয় a =1, b =1, c =7, তাহলে আউটপুট হবে "ccaccbcc"
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি ডেটা স্ট্রাকচার সংজ্ঞায়িত করুন যেখানে অক্ষর a, inx এবং cnt উপস্থিত রয়েছে
-
একটি অগ্রাধিকার সারি pq সংজ্ঞায়িত করুন, এটি ডেটার cnt মান ব্যবহার করে অগ্রাধিকার দেবে
-
a যদি অ-শূন্য হয়, তাহলে −
-
pq
-এ নতুন ডেটা('a', a, 0) সন্নিবেশ করান
-
-
যদি b অ-শূন্য হয়, তাহলে −
-
pq
-এ নতুন ডেটা ('b', b, 0) সন্নিবেশ করান
-
-
যদি c অ-শূন্য হয়, তাহলে −
-
pq
-এ নতুন ডেটা ('c', c, 0) সন্নিবেশ করান
-
-
idx :=1
-
ret :=ফাঁকা স্ট্রিং
-
সত্য যখন অ-শূন্য, কর −
-
temp :=pq এর শীর্ষ উপাদান
-
pq
থেকে উপাদান মুছুন -
যদি ret-এর আকার 0 না হয় এবং ret-এর শেষ উপাদানটি temp.a-এর মতো হয়, তাহলে −
-
যদি pq খালি হয়, তাহলে −
-
লুপ থেকে বেরিয়ে আসুন
-
-
x :=তাপমাত্রা
-
temp :=pq এর শীর্ষ উপাদান
-
pq
থেকে উপাদান মুছুন -
pq
-এ x ঢোকান
-
-
val :=0
-
যদি না হয় pq খালি এবং temp-এর cnt - pq <2 এর প্রথম উপাদানের cnt, তাহলে −
-
val :=1
-
-
অন্যথায়
-
val :=তাপমাত্রার সর্বনিম্ন cnt এবং 2
-
-
ret :=ret concatenate val index of temp.a থেকে val in end
-
temp.cnt :=temp.cnt - val
-
যদি pq খালি হয়, তাহলে −
-
লুপ থেকে বেরিয়ে আসুন
-
-
temp.idx :=idx
-
যদি temp.cnt> 0 হয়, তাহলে −
-
pq
-এ তাপমাত্রা সন্নিবেশ করান
-
-
(আইডিএক্স 1 দ্বারা বাড়ান)
-
-
রিটার্ন রিটার্ন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#include <bits/stdc++.h>
using namespace std;
struct Data{
char a;
int cnt;
int idx ;
Data(char c, int x, int k){
a = c;
cnt = x;
idx = k;
}
};
struct Cmp{
bool operator()(Data& a, Data& b) {
return !(a.cnt>b.cnt);
}
};
class Solution {
public:
string longestDiverseString(int a, int b, int c) {
priority_queue<Data, vector<Data>, Cmp> pq;
if (a)
pq.push(Data('a', a, 0));
if (b)
pq.push(Data('b', b, 0));
if (c)
pq.push(Data('c', c, 0));
int idx = 1;
string ret = "";
while (true) {
Data temp = pq.top();
pq.pop();
if (ret.size() && ret.back() == temp.a) {
if (pq.empty())
break;
Data x = temp;
temp = pq.top();
pq.pop();
pq.push(x);
}
int val = 0;
if (!pq.empty() && temp.cnt - pq.top().cnt < 2) {
val = 1;
}
else
val = min(temp.cnt, 2);
ret += string(val, temp.a);
temp.cnt -= val;
if (pq.empty())
break;
temp.idx = idx;
if (temp.cnt > 0)
pq.push(temp);
idx++;
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.longestDiverseString(1,1,7));
} ইনপুট
1,1,7
আউটপুট
ccbccacc
