สตริงไบนารีพิเศษใน C++

สมมติว่าเรามีสตริงไบนารีพิเศษ ที่มีคุณสมบัติ − จำนวน 0 และ 1 เท่ากัน และทุก Prefix มีจำนวน 1 มากกว่าหรือเท่ากับ 0

การเคลื่อนที่คือการเลือกสองสตริงย่อยพิเศษที่ติดกันและไม่ว่าง แล้วสลับกัน เราต้องหาสตริงที่ใหญ่ที่สุดในลำดับเล็กซิโครกราฟิกหลังการเคลื่อนที่กี่ครั้งก็ได้

เช่น 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; 
    } 
}; 

main(){ 
    Solution ob; 
    cout << (ob.makeLargestSpecial("11011000")); 
}

อินพุต

11011000

เอาต์พุต

11100100