ধরুন আমাদের একটি অ-খালি স্ট্রিং s এবং একটি পূর্ণসংখ্যা k আছে; আমাদের স্ট্রিংটিকে এমনভাবে সাজাতে হবে যাতে একই অক্ষরগুলি একে অপরের থেকে কমপক্ষে k দূরত্বে থাকে। প্রদত্ত স্ট্রিংগুলি ছোট হাতের অক্ষরে রয়েছে। যদি স্ট্রিংগুলিকে পুনর্বিন্যাস করার কোন উপায় না থাকে, তাহলে আমরা একটি খালি স্ট্রিং করব।
সুতরাং, যদি ইনপুটটি s ="aabbcc", k =3 এর মত হয়, তাহলে আউটপুট হবে "abcabc" কারণ একই অক্ষরগুলি একে অপরের থেকে কমপক্ষে 3 দূরত্বে থাকে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
ret :=একটি খালি স্ট্রিং
-
একটি মানচিত্র m
সংজ্ঞায়িত করুন -
n :=s
এর আকার -
আরম্ভ করার জন্য i :=0, যখন i
-
(m[s[i]] 1 দ্বারা বৃদ্ধি করুন)
-
-
একটি অগ্রাধিকার সারি pq
সংজ্ঞায়িত করুন -
প্রতিটি কী-মানের জন্য এটিকে m তে যুক্ত করুন, −
করুন-
temp :=কী এবং এর মান সহ একটি জোড়া
-
pq
-এ তাপমাত্রা সন্নিবেশ করান -
(এটি 1 দ্বারা বাড়ান)
-
-
একটি deque dq
সংজ্ঞায়িত করুন -
যখন (pq খালি নয়), −
করুন-
curr :=pq এর শীর্ষ
-
pq
থেকে উপাদান মুছুন -
ret :=ret + curr.first
-
(curr.second 1 দ্বারা কমিয়ে দিন)
-
dq
এর শেষে curr সন্নিবেশ করান -
যদি dq>=k এর আকার হয়, তাহলে −
-
curr :=dq এর প্রথম উপাদান
-
dq
থেকে সামনের উপাদান মুছুন -
যদি curr.second> 0 হয়, তাহলে −
-
pq
-এ curr ঢোকান
-
-
-
-
যখন (dq খালি নয় এবং dq-এর প্রথম উপাদান 0 এর মতো), করো −
-
dq
থেকে সামনের উপাদান মুছুন
-
-
রিটার্ন করুন (যদি dq খালি হয়, তারপর রিট করুন, অন্যথায় ফাঁকা স্ট্রিং)
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
struct Comparator {
bool operator()(pair<char, int> a, pair<char, int> b) {
return !(a.second > b.second);
}
};
class Solution {
public:
string rearrangeString(string s, int k) {
string ret = "";
unordered_map<char, int> m;
int n = s.size();
for (int i = 0; i < n; i++) {
m[s[i]]++;
}
unordered_map<char, int>::iterator it = m.begin();
priority_queue<pair<char, int<, vector<pair<char, int>>,
Comparator> pq;
while (it != m.end()) {
pair<char, int> temp = {it->first, it->second};
pq.push(temp);
it++;
}
deque<pair<char, int>> dq;
while (!pq.empty()) {
pair<char, int> curr = pq.top();
pq.pop();
ret += curr.first;
curr.second--;
dq.push_back(curr);
// cout << ret << " " << dq.size() << endl;
if (dq.size() >= k) {
curr = dq.front();
dq.pop_front();
if (curr.second > 0)
pq.push(curr);
}
}
while (!dq.empty() && dq.front().second == 0)
dq.pop_front();
return dq.empty() ? ret : "";
}
};
main() {
Solution ob;
cout << (ob.rearrangeString("aabbcc", 3));
} ইনপুট
"aabbcc", 3
আউটপুট
bacbac
