একটি স্ট্রিং "হ্যাপি" যদি 'aaa', 'bbb', 'ccc' সাবস্ট্রিং হিসেবে না থাকে। তিনটি ইন্টিজার a,b,c দেওয়া আছে। সর্বোচ্চ দৈর্ঘ্যের হ্যাপি স্ট্রিং বের করতে হবে যেটিতে 'a' Höchst a বার, 'b' Höchst b বার, 'c' Höchst c বার থাকবে।
ইনপুট: a=1, b=1, c=7 → আউটপুট: "ccaccbcc" (বা অন্য কোনো বৈধ সর্বোচ্চ দৈর্ঘ্যের স্ট্রিং)
সমাধানের ধাপগুলো (গ্রিডি + প্রায়োরিটি কিউ):
প্রায়োরিটি কিউতে
Data{char, count, idx}রাখব, কাউন্ট অনুযায়ী প্রায়োরিটিসবচেয়ে বেশি কাউন্ট ওয়ালা ক্যারেক্টার নিব
যদি শেষ দুটি অক্ষর একই হয়, তবে দ্বিতীয় সেরা নিব
যদি টপ দুটির কাউন্টের পার্থক্য < 2 হয়, তবে ১ টি নিব, অন্যথায় ২ টি নিব
কাউন্ট আপডেট করে পিটি কিউতে ফিরিয়ে দিব
উদাহরণ
নিচের কোডটি দেখুন −
#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;
}
};
int main() {
Solution ob;
cout << (ob.longestDiverseString(1, 1, 7));
}
ইনপুট
1,1,7
আউটপুট
ccbccacc
