LeetCode 761. 特殊的二进制字符串
题目描述
特殊的二进制序列是具有以下两个性质的二进制序列:
- 0 的数量与 1 的数量相等。
- 二进制序列的每一个前缀码中 1 的数量不少于 0 的数量。
给定一个特殊的二进制序列 S,我们可以将其中任意相邻的两个 特殊子串 进行交换(这两个子串本身也是特殊串)。通过任意次这样的交换,求出所能得到的字典序最大的结果。
题目理解
这种特殊的二进制序列与有效的括号序列非常相似:把 1 看作左括号 (,把 0 看作右括号 ),则满足括号匹配的序列就是特殊串。例如 "1100" 对应 (()),"10" 对应 ()。多个特殊串可以并列,如 "1010" 对应 ()()。
题目允许交换任意两个 相邻的、并列的 特殊子串,目标是通过交换使得整个串的字典序最大。注意交换只能在并列的同一层子串之间进行,不能跨层交换。但是通过递归处理,我们可以让每一层内部达到最大,从而整体达到最大。
解题思路
本题的核心解法是 递归分解 + 排序:
- 分解:遍历原串,用计数器
cnt记录1和0的差值(1加 1,0减 1)。每当cnt归零,说明找到了一个完整的特殊子串(它一定以1开头、以0结尾)。将这些一级子串拆出来。 - 递归:对每个一级子串,去掉首尾的
1和0,其内部仍是一个特殊串(可能为空或更小的特殊串),递归调用函数处理内部,使其达到最大字典序,然后再重新加上首尾的1和0。 - 排序:得到当前层的所有一级子串(每个都已经内部最优)后,将它们按
a + b > b + a的规则降序排序,这样拼接后就能使当前层整体字典序最大。 - 拼接:将排序后的子串连接起来,返回结果。
算法步骤
- 如果
S长度 ≤ 2,直接返回S(特殊串只有可能是"10"或空串)。 - 初始化一个空的字符串列表
q用于存放一级子串,临时字符串s用于累积当前子串,计数器cnt = 0。 - 遍历
S的每个字符c:- 将
c加入s。 - 若
c == '1',cnt++;否则cnt--。 - 当
cnt == 0时,说明从上一个cnt归零点(或开头)到当前位置形成了一个一级特殊子串。- 取出
s的内部部分(去掉首尾),递归调用makeLargestSpecial得到内部最大串。 - 在外层重新包裹
'1'和'0',形成新的串,加入q。
- 取出
- 将

