题目分析

我们看到困难题，首先要有信心去解决它，要向之前做过的题目靠近。本题特殊的二进制序列，本质上就是括号的匹配问题，合法的括号表达式是怎么样的？是不是左括号和右括号相等，如果将左括号类比1，右括号类比0，是不是每一个前缀码中的1要大于等于0？

分治

交换相邻的特殊的二进制序列，又有些类似于冒泡排序。我们思考有字符串A，可以根据1的个数等于0的个数分解成A1、A2、A3…子序列，如果A1、A2、A3本身都是按照最大字典序排列的字符串、且按照字典序将A1、A2、A3从大到小排列后组成A，则A本身也是按照最大字典序排列的字符串。

通过上面的分析，发现本题具有将大的问题划分成若干个相同性质小问题的特点。

而且A1、A2、A3…每一个子序列，如果长度为2，则是10。否则前面两位一定是1，后面两位一定是0。

第一位一定是1，否则都不满足序列的特性。第二位如果是0，则可以拆成长度为2的子序列，例如10XXXX，可以拆分成10 + XXXX。

最后一位一定是0，如果是1，则没有0与之匹配，不满足1的数量等于0的数量。倒数第二位一定是0，如果是1，也可以拆分成XXXX + 10。

因此找到子序列A1后，我们去掉子序列的第一位1和最后一位0，然后递归对子序列进行排序。

这里解释一下为什么要去掉第一位1和最后一位0，如果不去掉，则A1只能分解出A1本身，因为A的最后一位是0，因此所有前缀1的数量一定都是比0多的，所以根据1的个数等于0的个数无法继续分解。

因此本题最关键的一步代码是
list.add("1" + makeLargestSpecial(s.substring(left + 1, right)) + "0");

本题对于父问题要遍历整个字符串拆分成若干个子串，对于每个子串也需要遍历其所有字符，因此算法的**时间复杂度为$O(n^2)$，要对字符串进行排序，要保留每一段子串，其空间复杂度是$O(n)$**。

下面是Java语言的题解

class Solution {
    public String makeLargestSpecial(String s) {
        if (s.length() <= 2) {
            return s;
        }
        int sum = 0;
        int left = 0;
        ArrayList<String> list = new ArrayList<>();
        for (int right = 0; right < s.length(); right++) {
            sum += s.charAt(right) == '1' ? 1 : -1;
            if (sum == 0) {
                list.add("1" + makeLargestSpecial(s.substring(left + 1, right)) + "0");
                left = right + 1;
            }
        }
        list.sort((o1, o2) -> (o2 + o1).compareTo(o1 + o2));
        StringBuilder builder = new StringBuilder();
        for (String str : list) {
            builder.append(str);
        }
        return builder.toString();
    }
}

刷题总结

分治题目相对较少，但是都有明显的特征，就是看父问题能不能拆分成若干子问题，而且子问题解决后，能不能对父问题提供帮助。典型的题目就是归并排序，小伙伴们要深刻理解本题和归并排序的解题思路。