1.题目基本信息

1.1.题目描述

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

• 0 的数量与 1 的数量相等。

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

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

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

1.2.题目地址

https://leetcode.cn/problems/special-binary-string/description/

2.解题方法

2.1.解题思路

递归

2.2.解题步骤

第一步，递归函数的定义。定义「弱特殊二进制序列」为任何前缀中1的数量大于等于0的数量，且整体中0和1的个数相等的二进制字符串（可以理解为合法的括号组合）。递归函数传入一个「弱特殊二进制序列」，返回交换后字典序最大的字符串；假如s1为「弱特殊二进制序列」，可以通过前缀和为0划分为若干个最小单元的「特殊二进制序列」，并对每个「特殊二进制序列」进行递归操作，并将返回结果进行拼接返回

第二步，递归出口，当「弱特殊二进制序列」的长度小于等于2时，直接返回

第三步，pre维护最小单位的「特殊二进制序列」的起始索引位置，preSum维护前缀和（将0看成-1计算），arr维护各个最小单位的「特殊二进制序列」递归处理结果构成的数组；遍历s1，根据preSum找最小单位的「特殊二进制序列」，并进行递归处理

第四步，将arr进行「全序排列」，即a+b<b+a时认为a<b，一种字符串排序的常见方法

3.解题代码

python3代码

from functools import cmp_to_key

def compare(x, y):
    if x + y < y + x:
        return 1
    elif x + y > y + x:
        return -1
    else:
        return 0

class Solution:
    # 思路：递归
    def makeLargestSpecial(self, s: str) -> str:
        # 第一步，递归函数的定义。定义「弱特殊二进制序列」为任何前缀中1的数量大于等于0的数量，且整体中0和1的个数相等的二进制字符串（可以理解为合法的括号组合）。递归函数传入一个「弱特殊二进制序列」，返回交换后字典序最大的字符串；假如s1为「弱特殊二进制序列」，可以通过前缀和为0划分为若干个最小单元的「特殊二进制序列」，并对每个「特殊二进制序列」进行递归操作，并将返回结果进行拼接返回
        def dfs(s1) -> str:
            n = len(s1)
            # 第二步，递归出口，当「弱特殊二进制序列」的长度小于等于2时，直接返回
            if n <= 2:
                return s1
            # 第三步，pre维护最小单位的「特殊二进制序列」的起始索引位置，preSum维护前缀和（将0看成-1计算），arr维护各个最小单位的「特殊二进制序列」递归处理结果构成的数组；遍历s1，根据preSum找最小单位的「特殊二进制序列」，并进行递归处理
            pre = 0
            preSum = 0
            arr = []
            for i in range(n):
                preSum += (1 if s1[i] == "1" else -1)
                if preSum == 0:
                    arr.append("1" + dfs(s1[pre + 1: i]) + "0")
                    pre = i + 1
            # 第四步，将arr进行「全序排列」，即a+b<b+a时认为a<b，一种字符串排序的常见方法
            arr.sort(key = cmp_to_key(compare))
            return "".join(arr)
        return dfs(s)

4.执行结果