मान लीजिए हमारे पास एक स्ट्रिंग S है, जांचें कि क्या अक्षरों को पुनर्व्यवस्थित किया जा सकता है ताकि एक दूसरे से सटे दो वर्ण समान न हों। यदि यह संभव है, तो कोई भी संभावित परिणाम आउटपुट करें। यदि संभव नहीं है, तो खाली स्ट्रिंग वापस करें। उदाहरण के लिए, यदि इनपुट "AAB" है, तो आउटपुट "ABA" होगा।
हल करने के चरण
- इंटीजर-कैरेक्टर पेयर की एक प्रायोरिटी क्यू pq बनाएं, एक मैप m परिभाषित करें
- n := स्ट्रिंग का आकार
- मैप m में वर्ण आवृत्ति स्टोर करें
- m में प्रत्येक कुंजी-मान पेयर p के लिए
- (p का इंटीजर भाग, p का कैरेक्टर भाग) डालें
- ans := खाली स्ट्रिंग
- जब तक pq खाली नहीं है
- one := pq से शीर्ष पेयर लें, और pq से शीर्ष पेयर हटाएं
- यदि pq खाली है, तो
- यदि one का इंटीजर भाग > 1, तो खाली स्ट्रिंग वापस करें
- ans := ans + one का कैरेक्टर भाग
- ans वापस करें
- two := pq से शीर्ष पेयर लें, और pq से शीर्ष पेयर हटाएं
- ans := ans + one का कैरेक्टर भाग
- ans := ans + two का कैरेक्टर भाग
- one और two के इंटीजर भाग को 1 से घटाएं
- यदि one का इंटीजर भाग 0 नहीं है, तो one को pq में डालें
- यदि two का इंटीजर भाग 0 नहीं है, तो two को pq में डालें
- ans वापस करें
उदाहरण
#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; 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"
आउटपुट
ABA