सी ++ में स्ट्रिंग के दूरी के अलावा पुनर्व्यवस्थित करें

मान लीजिए कि हमारे पास एक गैर-रिक्त स्ट्रिंग s और एक पूर्णांक k है; हमें स्ट्रिंग को इस तरह पुनर्व्यवस्थित करना होगा कि समान वर्ण एक दूसरे से कम से कम k दूरी पर हों। दिए गए तार छोटे अक्षरों में हैं। यदि स्ट्रिंग्स को पुनर्व्यवस्थित करने का कोई तरीका नहीं है, तो हम एक खाली स्ट्रिंग करेंगे।

इसलिए, यदि इनपुट s ="aabbcc", k =3 जैसा है, तो आउटपुट "abcabc" होगा, ऐसा इसलिए है क्योंकि समान अक्षर एक दूसरे से कम से कम 3 दूरी पर हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• रिट:=एक खाली स्ट्रिंग

• एक नक्शा परिभाषित करें मी

• n :=s का आकार

• इनिशियलाइज़ i:=0 के लिए, जब i

  • (m[s[i]] 1 से बढ़ाएं)

• एक प्राथमिकता कतार pq परिभाषित करें

• प्रत्येक की-वैल्यू पेयर के लिए इसे m में जोड़ें -

  • अस्थायी:=एक जोड़ी कुंजी और इसके मूल्य के साथ

  • pq में अस्थायी डालें

  • (इसे 1 से बढ़ाएं)

• एक डेक डीक्यू परिभाषित करें

• जबकि (pq खाली नहीं है), करें -

  • curr :=pq के ऊपर

  • pq से तत्व हटाएं

  • रिट :=रिट + curr.first

  • (कर्र.सेकंड को 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