একটি বিশেষ বাইনারি স্ট্রিংের নিচের বৈশিষ্ট্যগুলো থাকে:
- ০ এবং ১-এর সংখ্যা সমান থাকে।
- স্ট্রিংয়ের যেকোনো প্রিফিক্সে ১-এর সংখ্যা ০-এর সংখ্যার চেয়ে কম নয়।
একটি মুভ বলতে স্ট্রিংয়ের দুটি последовательный, খালি না হলে, বিশেষ সাবস্ট্রিং বেছে নিয়ে সেগুলো সোয়াপ করা। আমাদের কাজ হল যেকোনো সংখ্যক মুভের পর लेক্সিকোগ্রাফিক্যালি সর্বোচ্চ স্ট্রিংটি বের করা।
উদাহরণ
ইনপুট: 11011000 → আউটপুট: 11100100
ব্যাখ্যা: "10" এবং "1100" সাবস্ট্রিং দুটি সোয়াপ করা হয়েছে।
সমাধানের ধাপসমূহ
- স্ট্রিংকে স্মলার 스페শাল সাবস্ট্রিং-এ ভাগ করুন (কাউন্ট ০ হলে ভাগ করুন)।
- প্রতিটি সাবস্ট্রিংর জন্য রিকারসিভলি একই প্রক্রিয়া প্রয়োগ করুন।
- সাবস্ট্রিংগুলাকে ডিসেন্ডিং অর্ডারে সর্ট করুন।
- সেগুলো একসাথে যোগ করুন।
প্রোগ্রাম উদাহরণ
#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"));
}
ইনপুট
11011000
আউটপুট
11100100
