8.8 ~ 8.14 尽量坚持刷力扣的每日一题，锻炼大脑思维。更新中~~

761. 特殊的二进制序列【递归分治】

题目描述

思路

题目要求0和1的数量相同，我们可以看成()括号匹配，意思就是让括号有效匹配的情况下，尽量让大量的左括号在前面。并且第一个字符一定是1，最后一个字符一定是0，其实证明也好证明，如果第一个数字为0，则以第一个数字为前缀，就不满足题目中的第二个条件，如果最后一个字符是1，则前n- 1的前缀则也不满足第二个条件。我们可以剔除1和0的情况，继续进行分治讨论，知道s的长度小于等于2的情况，只有两种情况，就是10以及空字符串，直接返回即可。递归返回后，将所有特殊字符按降序返回。

AC代码

class Solution:
    def makeLargestSpecial(self, ss: str) -> str:
        # 内置函数
        def dfs(s):
            if len(s) <= 2:
                return s

            cnt, left = 0, 0
            subs = list()
            for i, ch in enumerate(s):
                if ch == '1':
                    cnt += 1
                else:
                    cnt -= 1
                    # 找到一组特殊序列
                    if cnt == 0:
                        subs.append("1" + dfs(s[left + 1:i]) + "0")
                        left = i + 1
            subs.sort(reverse=True)
            return "".join(subs)

        return dfs(ss)