सी++ में विशेष बाइनरी स्ट्रिंग

मान लीजिए कि हमारे पास एक स्थानिक बाइनरी स्ट्रिंग है। इस स्ट्रिंग में निम्नलिखित कुछ गुण हैं -

• 0 और 1 की संख्या समान होती है

• बाइनरी स्ट्रिंग में प्रत्येक उपसर्ग में कम से कम 1s जितना 0s होता है

अब मान लें कि हमारे पास विशेष स्ट्रिंग एस है, एक चाल वास्तव में दो लगातार, गैर-खाली, एस के विशेष सबस्ट्रिंग का चयन करना और उन्हें स्वैप करना है।

हमें किसी भी चाल के अंत में, लेक्सिकोग्राफ़िक रूप से सबसे बड़ी परिणामी स्ट्रिंग को खोजना होगा।

इसलिए, यदि इनपुट 11011000 की तरह है, तो आउटपुट 11100100 होगा, ऐसा इसलिए है क्योंकि:सबस्ट्रिंग "10" और "1100" की अदला-बदली की जाती है। कुछ चालों के बाद यह शब्दावली की दृष्टि से सबसे बड़ी स्ट्रिंग है।

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

• फ़ंक्शन को परिभाषित करें makeLargestSpecial(), इसमें कुछ समय लगेगा,

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

• स्ट्रिंग्स की एक सरणी v परिभाषित करें

• मैं :=0

• प्रारंभ करने के लिए j :=0, cnt :=0, जब j

  • अगर s[j] '1' के समान है, तो -

    • (cnt 1 से बढ़ाएँ)

  • अन्यथा

    • (cnt 1 से घटाएं)

  • यदि cnt 0 के समान है, तो -

    • v

      के अंत में "1" + makeLargestSpecial (इंडेक्स i + 1 से j - i - 1) में s का सबस्ट्रिंग डालें

    • मैं :=जे + 1

• सरणी को क्रमबद्ध करें v.r

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

  • रिट:=रिट + वी[i]

• वापसी रिट

• मुख्य विधि से स्ट्रिंग के साथ makeLargestSpecial() को कॉल करें।

#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;
   }
};
main(){
   Solution ob;
   cout << (ob.makeLargestSpecial("11011000"));
}

11011000

11100100