解题思路

相信好多人看到题目中 “特殊的二进制序列” 的定义就懵逼了，这到底是什么鬼？
所以题目最难的地方就是 “不说人话”。其实只要想到这种定义就是 “有效的括号字符串” 就容易许多了，“1” 代表 “(”，“0” 代表 “)”。

• 0 和 1 的数量相等。 → “右括号” 数量和 “左括号” 相同。
• 二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。→ “右括号” 必须能够找到一个 “左括号” 匹配。

再看题目中 “操作” 的定义：首先选择 S 的两个 连续 且非空的 特殊 的子串，然后将它们交换。
翻译过来就是：选择 S 中的两个 相邻 的 有效的括号字符串，然后交换即可。

现在再来解决问题。首先分析 “有效的括号字符串” 的性质。

• 一个有效的括号字符串一般能够被拆分为一段或几段，其中每一段都是 “不可拆分的有效的括号字符串”，比如，“()(())” 可以拆分为 “()” 和 “(())”。
• 另外，“有效的括号字符串” 中的每一 “段” 内部 （即去掉最外层括号的字串）都是另一个 “有效括号字符串”，比如 “(())” 里面是 “()”。

根据上面的规则，我们可以 递归地 将二进制序列对应的 “括号字符串” 分解。以序列 “110011100110110000” 为例：

我们容易想到一种 递归地 解题思路。

• 第一步，将字符串拆分成一段或几段 “不可拆分的有效的括号字符串”。
• 第二步，将每一段 内部 的子串（也是 “有效的括号字符串”）分别重新排列成字典序最大的字符串（解决子问题）。
• 第三步，由于 每一对相邻的段都可以交换，因此无限次交换相当于我们可以把各个段以 任意顺序 排列。我们要找到字典序最大的排列。
  这里有一个值得思考的地方：由于每一 “段” 必会以 “0” 结尾，因此只要将 “字典序最大” 的串放在第一位，“字典序次大” 的串放在第二位，...，就可以得到字典序最大的排列。（即将各个段按照字典序从大到小排序即可）。

代码

###python

class Solution:
    def makeLargestSpecial(self, s: str) -> str:
        cur, last = 0, 0
        ret = []
        for i in range(len(s)):
            cur += 1 if s[i] == '1' else -1
            if cur == 0:
                ret.append('1' + self.makeLargestSpecial(s[last + 1 : i]) + '0')
                last = i + 1
        return ''.join(sorted(ret, reverse=True))

###c++

class Solution {
public:
    string makeLargestSpecial(string s) {
        vector<string> v;
        for(int i = 0, cur = 0, last = 0; i < s.size(); ++i) {
            (s[i] == '1')? cur++ : cur--;
            if(cur == 0) {
                v.push_back("1");
                v.back() += makeLargestSpecial(s.substr(last + 1, i - last - 1)) + '0';
                last = i + 1;
            }
        }
        sort(v.begin(), v.end(), greater<string>());

        string res;
        for(auto& r : v) {
            res += r;
        }
        return res;
    }
};