761. 特殊的二进制序列(分治)

761. 特殊的二进制序列(分治)

可等价为括号序列。

对于一个不可分割的括号序列显然 首位1和末位0不能操作。括号序列每个左括号唯一对应一个右括号。

因此我们可以对每一个原串的每个括号子串进行递归处理，处理到不可分割的括号序列之后就可以进行递归返回了，然后再对他们进行排序。

class Solution {
    
public:
    string makeLargestSpecial(string s) {
    
        if (s.size() <= 2) {
    
            return s;
        }
        int cnt = 0, left = 0;
        vector<string> subs;
        for (int i = 0; i < s.size(); ++i) {
    
            if (s[i] == '1') {
    
                ++cnt;
            }
            else {
    
                --cnt;
                if (cnt == 0) {
    
                    subs.push_back("1" + makeLargestSpecial(s.substr(left + 1, i - left - 1)) + "0");
                    left = i + 1;
                }
            }
        }

        sort(subs.begin(), subs.end(), greater<string>{
    });
        string ans = accumulate(subs.begin(), subs.end(), ""s);
        return ans;
    }
};