समस्या विवरण
एक विशेष बाइनरी स्ट्रिंग के निम्न गुण होते हैं:
- 0s और 1s की संख्या समान होती है।
- हर प्रीफिक्स (prefix) में 0s से कम या बराबर 1s होते हैं।
एक चाल में, S के दो लगातार, गैर-खाली, विशेष सबस्ट्रिंग्स को चुना जाता है और उन्हें स्वैप किया जाता है। हमें किसी भी संख्या में चालों के बाद लेक्सिकोग्राफिकली (lexicographically) सबसे बड़ी परिणामी स्ट्रिंग ज्ञात करनी है।
उदाहरण
इनपुट
11011000
आउटपुट
11100100
व्याख्या
सबस्ट्रिंग्स "10" और "1100" को स्वैप किया गया। यह कुछ चालों के बाद संभव लेक्सिकोग्राफिकली सबसे बड़ी स्ट्रिंग है।
समाधान दृष्टिकोण (पुनरावर्ती + सॉर्टिंग)
- स्ट्रिंग को प्राथमिक विशेष सबस्ट्रिंग्स में विभाजित करें (काउंटर का उपयोग करके: 1 के लिए +1, 0 के लिए -1; जब काउंटर 0 हो जाए)।
- प्रत्येक प्राथमिक सबस्ट्रिंग के लिए, उसके आंतरिक भाग (पहले और अंतिम अक्षर को छोड़कर) पर पुनरावर्ती रूप से लागू करें।
- प्रत्येक प्राथमिक सबस्ट्रिंग को "1" + पुनरावर्ती_परिणाम + "0" में लपेटें।
- सभी प्राथमिक सबस्ट्रिंग्स को अवरोही क्रम (descending order) में क्रमबद्ध करें।
- उन्हें जोड़कर परिणाम प्राप्त करें।
कार्यकारी प्रोग्राम
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string makeLargestSpecial(string s) {
string ret = "";
vector<string> v;
int i = 0;
for (int j = 0, cnt = 0; j < s.size(); j++) {
if (s[j] == '1') cnt++;
else cnt--;
if (cnt == 0) {
v.push_back("1" + makeLargestSpecial(s.substr(i + 1, j - i - 1)) + "0");
i = j + 1;
}
}
sort(v.rbegin(), v.rend()); // अवरोही क्रम
for (int i = 0; i < v.size(); i++) ret += v[i];
return ret;
}
};
int main() {
Solution ob;
cout << ob.makeLargestSpecial("11011000");
return 0;
}
आउटपुट
11100100
