题目描述

Special binary strings are binary strings with the following two properties:

The number of 0’s is equal to the number of 1’s.

Every prefix of the binary string has at least as many 1’s as 0’s.

Given a special string S, a move consists of choosing two consecutive, non-empty, special substrings of S, and swapping them. (Two strings are consecutive if the last character of the first string is exactly one index before the first character of the second string.)

At the end of any number of moves, what is the lexicographically largest resulting string possible?

Example 1:

Input: S = "11011000"
Output: "11100100"
Explanation:
The strings "10" [occuring at S[1]] and "1100" [at S[3]] are swapped.
This is the lexicographically largest string possible after some number of swaps.

Note:

1. S has length at most 50.
2. S is guaranteed to be a special binary string as defined above.

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

• 0 的数量与 1 的数量相等。
• 二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。
  题意:给定一个特殊的二进制序列 S，以字符串形式表示。定义一个操作 为首先选择 S 的两个连续且非空的特殊的子串，然后将它们交换。（两个子串为连续的当且仅当第一个子串的最后一个字符恰好为第二个子串的第一个字符的前一个字符。)在任意次数的操作之后，交换后的字符串按照字典序排列的最大的结果是什么？

算法1

$

题解：特殊二进制字符串其实很很像括号对匹配问题。首先我们可以观察到特殊二进制字符串必然是首位为1，末尾为0。其次我们需要观察得到如果S是特殊二进制字符串，那么有两种情况：

• S能够拆分为多个二进制字符串如 101100 = 10 + 1100，去除掉首尾的1和0得到的1001不是特殊二进制字符串。类似于(())()
• S只由一个特殊二进制字符串组成11100100，但是对于这种情况，我们可以除去首尾的1和0得到110010仍然是一个特殊二进制字符串。类似于((())())。

如果S能够被拆分为多个特殊二进制字符串，那么肯定是将比较长二进制字符串放在前面更好。对于不能被拆分成多个二进制字符串的，因为最外层的一对10不能动，我们则需要将其内部的二进制串整理成前缀最大的。

因此，类似于括号匹配，使用cnt记号标记当前有多少个左括号，当cnt==0时，说明左边是一个完整的二进制字符串，递归对其内部处理，最后将递归处理好的字符串从大到小排序。

C++ 代码

    string makeLargestSpecial(string S) {
        int n = S.length(), cnt = 0,i = 0;
        vector<string> res;
        string ans = "";
        if(n == 0) return ans;
        for(int j = 0; j < n;j ++)
        {
            if(S[j] == '1') cnt ++;
            else cnt --;
            if(cnt == 0)
            {
                res.push_back("1" + makeLargestSpecial(S.substr(i + 1,j - i - 1)) + "0");
                i = j + 1;
            }
        }
        sort(res.begin(),res.end());
        for(int i = res.size() - 1; i >= 0 ; i--)
            ans += res[i];
        return ans;    
    }