C++ এ বিশেষ বাইনারি স্ট্রিং

ধরুন আমাদের একটি স্থানিক বাইনারি স্ট্রিং আছে। এই স্ট্রিংটির নিম্নলিখিত কয়েকটি বৈশিষ্ট্য রয়েছে -

• একই সংখ্যক 0 এবং 1s আছে

• বাইনারি স্ট্রিং-এর প্রতিটি উপসর্গে কমপক্ষে 1s 0s

  থাকে

এখন ধরুন আমাদের স্পেশাল স্ট্রিং S আছে, একটি মুভ আসলে S-এর পরপর দুটি, অ-খালি, বিশেষ সাবস্ট্রিং বেছে নেওয়া এবং সেগুলিকে অদলবদল করছে৷

যেকোন সংখ্যক চালের শেষে আমাদের সম্ভাব্য অভিধানিকভাবে সবচেয়ে বড় ফলাফলের স্ট্রিং খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি 11011000 এর মত হয়, তাহলে আউটপুট হবে 11100100, এর কারণ হল:"10" এবং "1100" সাবস্ট্রিংগুলি অদলবদল করা হয়েছে৷ এটি আভিধানিকভাবে সবচেয়ে বড় স্ট্রিং যা কিছু পদক্ষেপের পরে সম্ভব।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন সংজ্ঞায়িত করুন makeLargestSpecial(), এটি s,

  লাগবে

• ret :=খালি স্ট্রিং

• স্ট্রিংগুলির একটি অ্যারে v সংজ্ঞায়িত করুন

• i :=0

• আরম্ভ করার জন্য j :=0, cnt :=0, যখন j

  • যদি s[j] '1' এর মত হয়, তাহলে −

    • (1 দ্বারা cnt বাড়ান)

  • অন্যথায়

    • (1 দ্বারা cnt হ্রাস)

  • যদি cnt 0 এর মত হয়, তাহলে −

    • v

      এর শেষে "1" + makeLargestSpecial (index i + 1 থেকে j - i - 1 পর্যন্ত s-এর সাবস্ট্রিং) সন্নিবেশ করুন

    • i :=j + 1

• অ্যারে সাজান v.r

• আরম্ভ করার জন্য i :=0, যখন i

  • ret :=ret + v[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