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

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

题目描述

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

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

给定一个特殊的二进制序列 S，我们可以将其中任意相邻的两个 特殊子串 进行交换（这两个子串本身也是特殊串）。通过任意次这样的交换，求出所能得到的字典序最大的结果。

题目理解

这种特殊的二进制序列与有效的括号序列非常相似：把 1 看作左括号 (，把 0 看作右括号 )，则满足括号匹配的序列就是特殊串。例如 "1100" 对应 (())，"10" 对应 ()。多个特殊串可以并列，如 "1010" 对应 ()()。

题目允许交换任意两个 相邻的、并列的 特殊子串，目标是通过交换使得整个串的字典序最大。注意交换只能在并列的同一层子串之间进行，不能跨层交换。但是通过递归处理，我们可以让每一层内部达到最大，从而整体达到最大。

解题思路

本题的核心解法是 递归分解 + 排序：

1. 分解：遍历原串，用计数器 cnt 记录 1 和 0 的差值（1 加 1，0 减 1）。每当 cnt 归零，说明找到了一个完整的特殊子串（它一定以 1 开头、以 0 结尾）。将这些一级子串拆出来。
2. 递归：对每个一级子串，去掉首尾的 1 和 0，其内部仍是一个特殊串（可能为空或更小的特殊串），递归调用函数处理内部，使其达到最大字典序，然后再重新加上首尾的 1 和 0。
3. 排序：得到当前层的所有一级子串（每个都已经内部最优）后，将它们按 a + b > b + a 的规则降序排序，这样拼接后就能使当前层整体字典序最大。
4. 拼接：将排序后的子串连接起来，返回结果。

算法步骤

1. 如果 S 长度 ≤ 2，直接返回 S（特殊串只有可能是 "10" 或空串）。
2. 初始化一个空的字符串列表 q 用于存放一级子串，临时字符串 s 用于累积当前子串，计数器 cnt = 0。
3. 遍历 S 的每个字符 c：
   • 将 c 加入 s。
   • 若 c == '1'，cnt++；否则 cnt--。
   • 当 cnt == 0 时，说明从上一个 cnt 归零点（或开头）到当前位置形成了一个一级特殊子串。
     • 取出 s 的内部部分（去掉首尾），递归调用 makeLargestSpecial 得到内部最大串。
     • 在外层重新包裹 '1' 和 '0'，形成新的串，加入 q。