LeetCode 761 特殊的二进制序列

Description

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

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

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

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

Solution

题目描述可以概括为如下内容：

• 要求是对给定字符串进行排序，并且被排序的元素为01组成的特殊序列
• 特殊序列01相等，并且前缀中1的数量大于0的数量->第一位肯定是1，最后一位肯定是0，否则无法保证前缀

首先介绍一个结论：如果一个序列中，相邻的元素可以相互交换，那么一定可以通过冒泡排序的方法进行任意的排序，以得到字典序最大或最小的序列。

因为进行排序的对象为01特殊序列，因此对给定序列进行划分，不断地分割出特殊的子序列，首先在子序列内部进行递归排序，得到最大的子序列，然后子序列之间进行排序，得到完整的序列。递归的终止条件为输入字符串的长度小于等于2时，直接返回。并且由于特殊序列的第一位一定是1，末位一定是0，因此在向下传参时可以将首位剥离。

完整的代码如下:

class Solution {
public:
    string makeLargestSpecial(string s) {
        if (s.size() <= 2) return s;
        int count = 0;
        vector<string> store;
        int left = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '1') 
                count++; 
            else
                count--;
            // count == 0表示前半序列0的数量和1的数量相等，同时我还要判断后面的半个序列是否满足要求
            if (count == 0) {
                store.push_back("1" + makeLargestSpecial(s.substr(left + 1, i - left - 1)) + "0");
                left = i + 1;
            }
        }
        sort(store.begin(), store.end(), greater<string>{});
        string res;
        for (auto iter = store.begin(); iter != store.end(); iter++) {
            res += *iter;
        }
        return res;
    }
};