761. 特殊的二进制字符串
题目描述
特殊的二进制序列是具有以下两个性质的二进制序列：
- 0 和 1 的数量相等
- 二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量
给定一个特殊的二进制序列 S，以字符串形式表示。定义一个操作：对于两个特殊字符串 a 和 b，如果 a 的字典序大于 b，可以将 ab 替换为 ba。
要求返回经过任意次操作后，能得到的字典序最大的字符串。
示例 1：
输入: S = "11011000"
输出: "11100100"
解释:
将 "11011000" 分解为不可再分的特殊子串："1100" 和 "1100"
每个子串去掉外层括号后递归处理内部，得到 "10" 和 "10"
处理后的子串为 "1100" 和 "1100"
按字典序降序排列后拼接："1100" + "1100" = "11001100"
但内部可以进一步优化："1" + "10" + "0" = "1100"
最终通过交换得到 "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:
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:
# 找到一个完整的特殊子串 [start, i]
inner = self.makeLargestSpecial(s[start+1:i])
substrings.append("1" + inner + "0")
start = i + 1
substrings.sort(reverse=True)
return ''.join(substrings)
完整代码实现
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 跟踪：
i=0: '1', diff=1
i=1: '1', diff=2
i=2: '0', diff=1
i=3: '1', diff=2
i=4: '1', diff=3
i=5: '0', diff=2
i=6: '0', diff=1
i=7: '0', diff=0 -> 找到一个子串 [0,7]
等等，这样分解不对。重新分析：
i=0: '1', diff=1
i=1: '1', diff=2
i=2: '0', diff=1
i=3: '0', diff=0 -> 子串 [0,3] = "1100"
i=4: '1', diff=1
i=5: '1', diff=2
i=6: '0', diff=1
i=7: '0', diff=0 -> 子串 [4,7] = "1100"
分解结果：["1100", "1100"]
第二步：递归处理每个子串
"1100":
去掉外层 -> "10"
递归处理 "10" -> "10" (基本情况)
加上外层 -> "1" + "10" + "0" = "1100"
第三步：排序拼接
["1100", "1100"] 降序排序 -> ["1100", "1100"]
拼接 -> "11001100"
但等等，这不是 "11100100"。重新思考...
实际上，"11011000" 应该分解为：
- 外层是 "1...0"，内部是 "1011000"
- 内部再分解...
正确的分解是：
"11011000" = "1" + "101100" + "0"
内部 "101100" 再分解...
最终通过递归处理得到 "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]，去掉外层括号
2. 递归的边界条件
if len(s) <= 2:
return s # "10" 是最简单的特殊字符串
3. 排序的方向
# 降序排列得到最大字典序
substrings.sort(reverse=True)
扩展思考
1. 与括号问题的联系
这道题本质上是括号问题的变形：
- 特殊二进制字符串 = 合法括号序列
- 分解子串 = 找最外层括号对
- 排序 = 通过交换得到最大字典序
2. 如果要求最小字典序？
只需将排序改为升序即可：
substrings.sort() # 升序