leetcode 761. 特殊的二进制序列

题目描述

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

0 的数量与 1 的数量相等。
二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。

给定一个特殊的二进制序列 S，以字符串形式表示。定义一个操作为首先选择 S 的两个连续且非空的特殊的子串，然后将它们交换。（两个子串为连续的当且仅当第一个子串的最后一个字符恰好为第二个子串的第一个字符的前一个字符。)

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

示例 1:

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

说明:

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

题解——视作有效括号，逐层处理

思路

所谓特殊的二进制数列，其实就是有效的括号，将1视为左括号，0视为右括号，则

1和0的数目相等等价于左括号和右括号数目相等
每时每刻1的数目不小于0的数目等价于每时每刻左括号不少于右括号

这必然保证了括号的有效性，简单证明一下
使用反证法，假设有不有效的括号符合条件，那么，要么左括号多余，要么右括号多余

如果右括号多余，一定存在从头开始的某段序列，右括号多余左括号，与第二条矛盾
如果左括号多余，在满足左右括号数目相等的前提下，必然有至少一个左括号晚于原应与之匹配的右括号出现，那么它前面的序列就不满足第二条了。

既然如此，我们在思考时，可以将二进制序列看成括号。下面来研究如何交换。
为此，要引入括号分层的概念。对于一个括号序列，我们将没有嵌套关系的序列视为同一层，比如()(())中，()和(())就属于同一层。连续的同层括号序列就是所谓的连续且非空的特殊的子串。依题意，我们可以交换同一层的相邻括号序列任意次，其实就是可以不断交换任意两个。所以，应当将同一层的每个括号序列能得到的最大序列排序，从大到小依次累加。而如何找到每个括号序列能得到的最大序列呢？很自然地引入递归。

举个例子，对于示例11011000，也就是(()(()))，第一层就是它本身，第二层是(()(()))包括()和(())，(())中又产生第三层()，每增加一层，就要移除一次左右两边的括号。我们的算法这样进行：(()(()))同级括号只有它本身，所以搜索下一层，也就是()(())的最大序列，这里有两个同级序列()和(())，我们要依次找到他们的最大值，()就是本身，(())继续拆成()，返回后也是它本身，然后，我们可以交换()和(())，通过排序后相加，得到(())()，向上返回，到了第一层，最终答案就是((())())，也就是11100100。

代码

class Solution {
public:
    string makeLargestSpecial(string s) {
        vector<string> child;//保存同级的每个括号序列产生的最大序列
        int left=0,right=0,pos=0,beg=0;//left,right记录括号数，pos记录当前位置，beg记录开始位置
        while(pos<s.size())
        {
            ++(s[pos]=='1'?left:right);//如果是1，++left，否则++right
            if(left==right)//左右相抵，说明找到一个同级括号(至少有一个，就是它本身)
            {
                string max=makeLargestSpecial(s.substr(beg+1,pos-beg-1));//去掉外层括号，得到下一层并查找最大值 
                child.push_back("1"+max+"0");//将外层括号加回并保存进child
                beg=pos+1;
            }
            ++pos;
        }
        sort(child.begin(),child.end());//按字典序从小到大排列
        string ans;
        for(int i=child.size()-1;i>=0;--i)//从后往前加，得到本层答案
            ans+=child[i];
        return ans;
    }
};