ধরুন আমাদের একটি স্ট্রিং S আছে, অক্ষরগুলিকে পুনরায় সাজানো যায় কিনা তা পরীক্ষা করুন যাতে একে অপরের সংলগ্ন দুটি অক্ষর একই না হয়। যদি এটি সম্ভব হয়, তবে সম্ভাব্য ফলাফল আউটপুট করুন। যদি তা সম্ভব না হয়, খালি স্ট্রিংটি ফেরত দিন। তাই ইনপুট যদি “AAB” এর মত হয়, তাহলে আউটপুট হবে “ABA”।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- pq নামক পূর্ণসংখ্যা অক্ষর জোড়ার একটি অগ্রাধিকার সারি তৈরি করুন, একটি মানচিত্র m সংজ্ঞায়িত করুন
- n :=স্ট্রিংয়ের আকার
- ম্যাপে অক্ষর ফ্রিকোয়েন্সি সঞ্চয় করুন m
- প্রতিটি কী-মানের জোড়ার জন্য m
- এ p
- ঢোকান (p-এর পূর্ণসংখ্যা অংশ, p-এর অক্ষর অংশ)
- উত্তর :=খালি স্ট্রিং
- যখন pq খালি নয়
- একটি সেট করুন :=pq থেকে শীর্ষ জোড়া, এবং pq থেকে শীর্ষ জোড়া মুছে দিন
- যদি pq খালি হয়, তাহলে
- যদি একটি> 1 এর পূর্ণসংখ্যা অংশ হয়, তাহলে খালি স্ট্রিং ফেরত দিন
- উত্তর :=ans + একটি অক্ষর অংশ
- উত্তর ফেরত দিন
- দুই :=pq থেকে শীর্ষ জোড়া, এবং pq থেকে শীর্ষ জোড়া মুছে দিন
- উত্তর :=ans + একটি অক্ষর অংশ
- উত্তর :=ans + দুইটির অক্ষর অংশ
- এক এবং দুইটির পূর্ণসংখ্যার অংশ 1 দ্বারা বাড়ান
- যদি একটির পূর্ণসংখ্যা অংশ 0 না হয়, তাহলে একটিকে pq তে প্রবেশ করান
- যদি দুইটির পূর্ণসংখ্যার অংশ 0 না হয়, তাহলে একটিকে pq-তে ঢোকান
- উত্তর ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string reorganizeString(string S) {
priority_queue <pair <int, char>> pq;
map <char, int> m;
int n = S.size();
for(int i = 0; i < n; i++){
m[S[i]]++;
}
map <char, int> :: iterator i = m.begin();
while(i != m.end()){
pq.push({i->second, i->first});
i++;
}
string ans = "";
while(!pq.empty()){
pair <int, char> one = pq.top();
pq.pop();
if(pq.empty()){
if(one.first > 1)
return "";
ans += one.second;
return ans;
}
pair <int, char> two = pq.top();
pq.pop();
ans += one.second;
ans += two.second;
//cout << ans << endl;
one.first--;
two.first--;
if(one.first)pq.push(one);
if(two.first)pq.push(two);
}
return ans;
}
};
int main() {
Solution ob1;
cout << ob1.reorganizeString("AAB") << endl;
return 0;
} ইনপুট
S = "AAB"
ob1.reorganizeString("AAB") আউটপুট
ABA
