मान लीजिए हमारे पास एक गैर-खाली स्ट्रिंग s और एक पूर्णांक k है; हमें स्ट्रिंग को इस तरह पुनर्व्यवस्थित करना है कि समान वर्ण एक-दूसरे से कम से कम दूरी k पर हों। दी गई स्ट्रिंग्स लोअरकेस अक्षरों में हैं। यदि स्ट्रिंग्स को पुनर्व्यवस्थित करने का कोई तरीका नहीं है, तो हम एक खाली स्ट्रिंग लौटाएंगे।
तो, यदि इनपुट s = "aabbcc", k = 3 जैसा है, तो आउटपुट "abcabc" होगा क्योंकि समान अक्षर एक-दूसरे से कम से कम दूरी 3 पर हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
ret := एक खाली स्ट्रिंग
एक मैप m परिभाषित करें
n := s का आकार
i := 0 से आरंभ करें, जब i < n, अद्यतन करें (i को 1 से बढ़ाएं), करें −
(m[s[i]] को 1 से बढ़ाएं)
एक प्राथमिकता कतार pq परिभाषित करें
m में प्रत्येक कुंजी-मान जोड़ी it के लिए, करें −
temp := it की कुंजी और मान के साथ एक जोड़ी
temp को pq में डालें
(it को 1 से बढ़ाएं)
एक डीक्यू dq परिभाषित करें
जब तक (pq खाली नहीं है), करें −
curr := pq का शीर्ष
pq से तत्व हटाएं
ret := ret + curr.first
(curr.second को 1 से घटाएं)
curr को dq के अंत में डालें
यदि dq का आकार >= k, तो −
curr := dq का पहला तत्व
dq से पहला तत्व हटाएं
यदि curr.second > 0, तो −
curr को pq में डालें
जब तक (dq खाली नहीं है और dq का पहला तत्व 0 के समान है), करें −
dq से पहला तत्व हटाएं
लौटाएं (यदि dq खाली है, तो ret, अन्यथा खाली स्ट्रिंग)
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
#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
