761. 特殊的二进制字符串
题目描述
特殊的二进制序列是具有以下两个性质的二进制序列：
- 0 和 1 的数量相等
- 二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量
给定一个特殊的二进制序列 S，以字符串形式表示。定义一个操作：对于两个特殊字符串 a 和 b，如果 a 的字典序大于 b，可以将 ab 替换为 ba。
要求返回经过任意次操作后，能得到的字典序最大的字符串。
示例 1：
输入：s = "11011000"
输出："11100100"
解释:
"11011000" 去掉最外层括号后，内部是 "101100"，可以分解为 "10" 和 "1100" 两个特殊子串
"1100" 的字典序大于 "10"，交换后内部变为 "1100" + "10" = "110010"
装回外层括号得到 "1" + "110010" + "0" = "11100100"
示例 2：
输入：s = "10"
输出："10"
解题思路
第一步：理解问题本质
特殊二进制字符串 = 合法括号序列
- 把 1 看作左括号
( - 把 0 看作右括号
)
这样，特殊二进制字符串的条件就转化为：
- 左右括号数量相等
- 任意前缀中左括号数量 >= 右括号数量
这正是合法括号序列的定义！
第二步：理解操作的本质
题目允许的操作：如果 a > b（字典序），可以将 ab 替换为 ba。
关键洞察： 这个操作实际上就是交换相邻的特殊子串！
通过不断交换，可以将子串按任意顺序排列。因此，问题转化为： 将特殊字符串分解为若干子串，排序后拼接得到最大字典序。
第三步：分解特殊字符串
不可再分的特殊子串：
- 类似于「原子」的概念，不能再分解为更小的特殊子串
- 在括号表示中，就是最外层的匹配括号对
分解方法：
- 使用「平衡因子」diff = 1 的个数 - 0 的个数
- 当 diff 从 0 变回 0 时，就找到了一个完整的特殊子串
第四步：递归处理
对于每个特殊子串：
- 去掉外层括号（首位的 1 和末位的 0）
- 递归处理内部
- 加上外层括号
- 所有子串排序后拼接
class Solution:
def makeLargestSpecial(self, s: str) -> str:
# 空串和 "10" 都没有可交换的内部，本身就是最优解
if len(s) <= 2:
return s
substrings = []
# diff = 1 的个数 - 0 的个数，相当于括号序列的平衡因子
diff = 0
start = 0
for i, ch in enumerate(s):
if ch == '1':
diff += 1
else:
diff -= 1
if diff == 0:
# 找到一个完整的特殊子串 [start, i]
# 首位的 1 和末位的 0 是最外层括号，只有内部可以重排
inner = self.makeLargestSpecial(s[start+1:i])
# 内部调成最大后，再把外层括号装回去
substrings.append("1" + inner + "0")
# 下一个子串从 i + 1 开始
start = i + 1
# 子串之间可以自由交换，把大的排前面才能让整体字典序最大
substrings.sort(reverse=True)
return ''.join(substrings)
完整代码实现
算法可视化 · 逐帧回放这道题的代码6 帧 · 录制输入 "11011000"
class Solution:
"""
特殊的二进制字符串 - 递归 + 排序
核心思路：
1. 特殊二进制字符串可以看作「合法括号序列」
2. 分解为不可再分的特殊子串
3. 每个子串去掉外层括号后递归处理
4. 按字典序降序排列后拼接
时间复杂度: O(n^2 log n)
空间复杂度: O(n)
"""
def makeLargestSpecial(self, s: str) -> str:
if len(s) <= 2:
return s
substrings = []
diff = 0
start = 0
for i, ch in enumerate(s):
if ch == '1':
diff += 1
else:
diff -= 1
if diff == 0:
inner = self.makeLargestSpecial(s[start+1:i])
substrings.append("1" + inner + "0")
start = i + 1
substrings.sort(reverse=True)
return ''.join(substrings)
示例推演
以 S = "11011000" 为例。diff 记录「1 比 0 多几个」，每回到 0 就切出一个特殊子串。
第一步：切出最外层子串
| 下标 | 字符 | diff | 说明 |
|---|---|---|---|
| 0 | 1 | 1 | |
| 1 | 1 | 2 | |
| 2 | 0 | 1 | |
| 3 | 1 | 2 | |
| 4 | 1 | 3 | |
| 5 | 0 | 2 | |
| 6 | 0 | 1 | |
| 7 | 0 | 0 | diff 归零，切出 [0, 7] |
中途 diff 从未归零，说明整个串只有一个最外层括号对：
"11011000" = "1" + "101100" + "0"。
第二步：递归处理内部 "101100"
- 下标 0..1 的
"10"：长度为 2，直接命中基本情况，返回"10" - 下标 2..5 的
"1100"：去掉外层得到"10"，递归返回"10"，再装回外层得"1100"
这一步得到两个子串 ["10", "1100"]。按字典序降序排列（"1100" > "10"），
拼接成 "110010"。
第三步：装回最外层
"1" + "110010" + "0" = "11100100"，与示例输出一致。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 递归+排序 | O(n^2 log n) | O(n) | 每层递归都需要遍历和排序 |
说明：
- n 是字符串长度
- 最坏情况下（如 "111...000..."），递归深度为 O(n)
- 每层需要 O(n) 的遍历和 O(n log n) 的排序
易错点总结
1. 分解条件的判断
# 当 diff 回到 0 时，找到一个完整的特殊子串
if diff == 0:
# 子串范围是 [start, i]
# 内部是 [start+1, i-1]，去掉外层括号
# 中途 diff 从未归零，说明这段不能再拆，是最外层的括号对
2. 递归的边界条件
if len(s) <= 2:
return s # "10" 是最简单的特殊字符串
# 少了这个出口，单字符 "1" 会被拆成空串返回，"10" 也要多绕一层递归
3. 排序的方向
# 降序排列得到最大字典序
substrings.sort(reverse=True)
# 升序会得到最小字典序，方向反了答案就完全相反
扩展思考
1. 与括号问题的联系
这道题本质上是括号问题的变形：
- 特殊二进制字符串 = 合法括号序列
- 分解子串 = 找最外层括号对
- 排序 = 通过交换得到最大字典序
2. 如果要求最小字典序？
只需将排序改为升序即可：
substrings.sort() # 升序
# 与求最大字典序相比，只改了排序方向，其余逻辑完全一样