স্ট্রিং S দেওয়া। ক্যারেক্টার রি-অ্যারেঞ্জ করে কোনো দুটি আডজেসেন্ট ক্যারেক্টার একই না হয় এমন স্ট্রিং বানাতে হবে। সম্ভব না হলে খালি স্ট্রিং রিটার্ন করুন।
উদাহরণ: "AAB" → "ABA"।
সমাধানের ধাপসমূহ
- ফ্রিকোয়েন্সি ম্যাপ বানান।
- ম্যাক্স-হিপ (প্রায়োরিটি কিউ) দিয়ে সবচেয়ে বেশি ফ্রিকোয়েন্সি वाला ক্যারেক্টার বেছে নিন।
- প্রতিবার টপ ২টি ক্যারেক্টার নিয়ে অল্টারনেট করুন, ফ্রিকোয়েন্সি কমিয়ে পুশ ব্যাক করুন।
- শেষে একটিই বাকি থাকলে (ফ্রিকোয়েন্সি > ১ হলে অসম্ভব) হ্যান্ডেল করুন।
C++ উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string reorganizeString(string S) {
unordered_map<char, int> freq;
for (char c : S) freq[c]++;
priority_queue<pair<int, char>> pq;
for (auto& p : freq) pq.push({p.second, p.first});
string ans;
while (!pq.empty()) {
auto one = pq.top(); pq.pop();
if (pq.empty()) {
if (one.first > 1) return "";
ans += one.second;
return ans;
}
auto two = pq.top(); pq.pop();
ans += one.second;
ans += two.second;
if (--one.first > 0) pq.push(one);
if (--two.first > 0) pq.push(two);
}
return ans;
}
};
int main() {
Solution ob;
cout << ob.reorganizeString("AAB");
}
ইনপুট
S = "AAB"
আউটপুট
ABA
