761. 特殊的二进制序列

题目：

特殊的二进制序列是具有以下两个性质的二进制序列：

0 的数量与 1 的数量相等。
二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。
给定一个特殊的二进制序列 S，以字符串形式表示。定义一个操作 为首先选择 S 的两个连续且非空的特殊的子串，然后将它们交换。（两个子串为连续的当且仅当第一个子串的最后一个字符恰好为第二个子串的第一个字符的前一个字符。)

在任意次数的操作之后，交换后的字符串按照字典序排列的最大的结果是什么？

---

示例 1:

输入: S = "11011000"
输出: "11100100"
解释:
将子串 "10" （在S[1]出现） 和 "1100" （在S[3]出现）进行交换。
这是在进行若干次操作后按字典序排列最大的结果。

---

说明:

S 的长度不超过 50。
S 保证为一个满足上述定义的特殊 的二进制序列。

---

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/special-binary-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

思路：

主要采取递归的方法来解决此问题。

详细在代码中已经标注出来了。

---

代码：

class Solution {
public:
    string makeLargestSpecial(string s) {
        int len = s.size();
        return Dfs(s, 0, len);
    }
    // 区间左闭右开（核心逻辑就是一层一层脱去外面的括号，让每一个子的都是特殊的）
    string Dfs(string s, int l, int r){
        // base case 超界限返回
        if (l >= r) {
            return "";
        }
        // 括号的对数
        int cnt = 0;
        // 当前的特殊子串的起始坐标（这个起始左边就是拆除的最外层括号的起始坐标）
        int pos = l;
        // 存放这层便利的所有特殊子串，供之后排序
        vector res;
        for (int i = l; i < r; i++) {
            if (s[i] == '1') cnt++;
            else cnt--; 
 
            // 统计出了一个特殊子串
            if (cnt == 0) {
                // 脱去最外层括号，继续拆里层的括号，且也是左闭右开
                string midRes = '1' + Dfs(s, pos + 1, i) + '0';
                res.emplace_back(midRes);
                pos = i + 1; // 以一个准备拆除的外括号的起始坐标，顺便也符合题意 
            }
        }
        // 逆序排，刚好也恰好符合了在任意次数的操作之后，交换后的字符串按照字典序排列的最大
        sort(res.rbegin(), res.rend());
        string ans = "";
        for (auto ss : res) {
            ans += ss;
        }
        // 返回给上层递归
        return ans;
    }
};