सी ++ में स्ट्रिंग को पुनर्गठित करें

मान लीजिए कि हमारे पास एक स्ट्रिंग S है, जांचें कि क्या अक्षरों को फिर से व्यवस्थित किया जा सकता है ताकि दो अक्षर जो एक दूसरे से सटे हों, समान न हों। यदि यह संभव है, तो किसी भी संभावित परिणाम को आउटपुट करें। यदि यह संभव नहीं है, तो खाली स्ट्रिंग लौटाएं। तो अगर इनपुट "एएबी" जैसा है, तो आउटपुट "एबीए" होगा।

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

• pq नामक पूर्णांक वर्ण युग्मों की एक प्राथमिकता कतार बनाएं, एक मानचित्र m परिभाषित करें
• n :=स्ट्रिंग का आकार
• वर्ण आवृत्ति को मानचित्र m में संग्रहीत करें
• प्रत्येक कुंजी-मान युग्म p के लिए m
  • सम्मिलित करें (p का पूर्णांक भाग, p का वर्ण भाग)
• उत्तर:=खाली स्ट्रिंग
• जबकि pq खाली नहीं है
  • एक सेट करें:=pq से शीर्ष जोड़ी, और pq से शीर्ष जोड़ी हटाएं
  • यदि pq खाली है, तो
    • यदि एक> 1 का पूर्णांक भाग है, तो खाली स्ट्रिंग लौटाएं
    • उत्तर:=उत्तर + एक का वर्ण भाग
    • वापसी उत्तर
  • दो :=pq से शीर्ष जोड़ी, और pq से शीर्ष जोड़ी हटाएं
  • उत्तर:=उत्तर + एक का वर्ण भाग
  • उत्तर:=उत्तर + दो का वर्ण भाग
  • एक और दो के पूर्णांक भाग को 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