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