特殊的二进制序列是具有以下两个性质的二进制序列：
- 0 的数量与 1 的数量相等。
- 二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。
给定一个特殊的二进制序列 S，以字符串形式表示。定义一个操作 为首先选择 S 的两个连续且非空的特殊的子串，然后将它们交换。（两个子串为连续的当且仅当第一个子串的最后一个字符恰好为第二个子串的第一个字符的前一个字符。)
在任意次数的操作之后，交换后的字符串按照字典序排列的最大的结果是什么？
示例 1:
输入: S = "11011000" 输出: "11100100" 解释: 将子串 "10" （在S[1]出现） 和 "1100" （在S[3]出现）进行交换。 这是在进行若干次操作后按字典序排列最大的结果。
说明:
S的长度不超过50。S保证为一个满足上述定义的特殊 的二进制序列。
标签：
['递归', '字符串']难度：Hard
喜欢：176- 先将字符串划分成同级括号序列
- 将同级括号序列进行排序，得到字典序最小的序列
- 递归上述过程
括号序列排序： 剑指 Offer 45. 把数组排成最小的数
递归分治分成
每层排序
总时间复杂度：$O(n^2logn)$
class Solution {
public:
string makeLargestSpecial(string S) {
if (S.size() <=2) return S;
vector<string> q; // 记录 同级括号，用来排序
string s;
int cnt = 0 ; // 判断 同级括号
for (char c: S) {
s+=c;
if (c=='1') cnt++;
else {
cnt--;
if (cnt == 0) {
q.push_back('1' + makeLargestSpecial(s.substr(1, s.size()-2)) + '0');
s.clear();
}
}
}
sort(q.begin(), q.end(), [](string&a, string&b){ // 同级括号 字典序最小
return a + b > b+a;
});
string res ;
for (auto x: q) res += x;
return res;
}
};