[LeetCode] 761. 特殊的二进制字符串

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

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

给定一个特殊的二进制字符串 s。

一次移动操作包括选择字符串 s 中的两个连续的、非空的、特殊子串，并交换它们。如果第一个字符串的最后一个字符与第二个字符串的第一个字符的索引相差正好为 1，则称两个字符串是连续的。

返回在字符串上应用任意次操作后可能得到的字典序最大的字符串。

示例 1:

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

示例 2：

输入：s = "10"
输出："10"

提示：

1 <= s.length <= 50
s[i] 为 '0' 或 '1'。
s 是一个特殊的二进制字符串。

思路:

首先得理解题目为什么要使用特殊二进制字符串。这种字符串当在从左往右读这个字符串时，在任何时刻读到的 1 的总数都不会少于 0 的总数，这意味着字符串不能以0开头(除非是空串），且0必须总是跟在某个未匹配的1后面。所以这种字符串就是一列互相嵌套的括号——或者说有序树(任意节点的子节点之间有顺序关系的树)，1表示左括号0表示右括号，以 "11011000"为例，这可理解为"(()(()))"。嚯，这看上去不就很熟悉了，递归分治搞起来。且题目允许交换连续的特殊子串，这意味着同一层级的所有特殊子串可以任意排列，为了得到字典序最大的结果，应该让字典序大的子串排在前面。因此只要一层层剥开给定的字符串，就能获得各层级的所有特殊子串，然后使用贪心策略把字典序最大的一个个拼接起来就好了。

AC代码:

class Solution {
public:
    string makeLargestSpecial(string s) {
        if (s.length() <= 2) {
            return s;
        }
        
        vector<string> substrings;
        int count = 0;
        int start = 0;
        
        for (int i = 0; i < s.length(); i++) {
            count += (s[i] == '1' ? 1 : -1);
            
            if (count == 0) {
                // 递归处理中间部分
                string inner = makeLargestSpecial(s.substr(start + 1, i - start - 1));
                substrings.push_back("1" + inner + "0");
                start = i + 1;
            }
        }
        
        sort(substrings.begin(), substrings.end(), greater<string>());
        
        string result = "";
        for (const string& sub : substrings) {
            result += sub;
        }
        
        return result;
    }
};Code language: C++ (cpp)

参考资料: