LeetCode 761. 特殊的二进制字符串 解题详解（Python 递归+排序）

LeetCode 761. 特殊的二进制字符串 解题详解Python 递归排序一、题目描述原题链接761. Special Binary String特殊的二进制字符串定义为满足以下两个条件的二进制序列字符串中0的数量与1的数量相等序列的每一个前缀包括空前缀中1的数量始终大于或等于0的数量。给定一个特殊的二进制字符串s允许的操作是选择字符串中两个连续的、非空的特殊子串并交换它们的位置。求经过任意次操作后能够得到的字典序最大的字符串。示例 1输入:s11011000输出:11100100解释:将子串10在 s[1]出现和1100在 s[3]出现交换得到最大字典序结果。示例 2输入:s10输出:10提示1 ≤ s.length ≤ 50s[i] 为0或1s 是一个特殊的二进制字符串二、题目分析2.1 特殊字符串的本质如果将1视为左括号(0视为右括号)那么“特殊的二进制字符串”恰好对应一个合法的括号序列0 和 1 数量相等 ⇔ 左右括号数量相等任意前缀中 1 ≥ 0 ⇔ 任意前缀中左括号数量不少于右括号数量。因此特殊字符串实质上就是一个有效括号字符串只是用1和0替代了(和)。2.2 操作规则的含义题目允许我们交换两个连续的、非空的特殊子串。由于特殊子串本身也是有效的括号串这个操作等价于在括号表达式中交换两个相邻的合法括号块。例如 ( ) [ ( ( ) ) ] → 交换 () 和 (()) → ( ( ) ) ( ) 通过多次交换相邻的合法括号块我们实际上可以对该层级的所有连续合法子串进行任意排列类似于冒泡排序。因此为了使整个字符串字典序最大我们应当将这些子串按降序排列。但要注意特殊字符串可能具有嵌套结构。对于形如1 内部特殊串 0的最外层结构内部仍是一个特殊的二进制字符串我们同样可以对内部进行优化。这种自相似性提示我们可以使用递归分治策略。三、核心思路递归分解 贪心排序3.1 分解规则对于一个非空的特殊字符串s我们可以通过一次遍历将其拆分为若干个不可再分的特殊子串即该子串的任何非空前缀都不再满足特殊条件除非是整个子串自身。具体做法维护一个计数器count遇到1则1遇到0则-1。当count 0时说明从上一个分割点到当前位置的子串是一个完整的特殊子串且为不可分的最小单位。例如对于s 11011000下标字符count备注011开始第一个子串112201312413502601700count 归零得到一个不可分子串 “11011000”咦这里只有一个整体因为我们是从头开始遍历但可以发现s中其实包含10和1100两个并列子串。实际上用上述方法拆分11011000时整个字符串被识别为一个不可分子串它的最外层是1.......0结构内部为101100。3.2 递归处理对于每个不可分的特殊子串它必然以1开头、以0结尾且中间部分也是一个特殊字符串可能为空。因此我们可以去掉首尾的1和0得到中间子串inner递归调用makeLargestSpecial(inner)得到字典序最大的内部排列在结果外层重新包裹1和0即1 递归(inner) 0将所有这样处理后的子串收集起来按字典序降序排序然后拼接返回。3.3 为什么这样贪心是正确的同一层级的多个特殊子串可以通过交换任意排序为了整体字典序最大显然应该让较大的子串排在前面。内部的特殊子串虽然被1...0包裹但其内部同样遵循相同的规则因此递归处理即可得到局部最优。数学归纳法可以证明通过递归和排序最终生成的字符串是全局最优的。四、算法步骤初始化若s为空直接返回空字符串。遍历字符串维护计数器count 0起始下标start 0。对于当前字符ch若ch 1count 1若ch 0count - 1。当count 0时说明s[start:i1]是一个不可分的特殊子串。递归处理子串提取子串sub s[start:i1]。内部字符串inner sub[1:-1]去掉首尾的1和0。递归得到sorted_inner self.makeLargestSpecial(inner)。构建新子串1 sorted_inner 0加入结果列表parts。更新start i 1。排序与合并对parts中的字符串按降序排序。拼接并返回最终结果。五、代码实现classSolution:defmakeLargestSpecial(self,s:str)-str:# 递归终止条件ifnots:returnparts[]# 存储当前层级的各个不可分子串count0# 平衡计数器start0# 当前子串的起始位置fori,chinenumerate(s):# 更新计数器ifch1:count1else:count-1# 当 count 归零找到了一个完整的不可分子串ifcount0:subs[start:i1]# 如 1100innersub[1:-1]# 去掉外层 1 和 0得到内部特殊串sorted_innerself.makeLargestSpecial(inner)# 递归处理内部parts.append(1sorted_inner0)# 重新包裹starti1# 更新下一个子串的起点# 当前层级的子串按字典序降序排列拼接得到最大结果parts.sort(reverseTrue)return.join(parts)六、复杂度分析时间复杂度O ( n 2 log ⁡ n ) O(n^2 \log n)O(n2logn)。其中n nn是字符串长度。每次递归会扫描字符串并将结果排序。在最坏情况下例如字符串呈现完全平衡的嵌套结构递归深度为O ( n ) O(n)O(n)每层扫描和排序的代价之和近似为O ( n 2 log ⁡ n ) O(n^2 \log n)O(n2logn)。由于n ≤ 50 n \le 50n≤50实际运行非常快。空间复杂度O ( n ) O(n)O(n)递归栈深度及临时列表parts的空间开销。七、示例详解示例 1s 11011000第一层遍历当i7时count首次归零得到一个整体子串11011000该层只有一个部分。去掉外层得内部inner 101100。递归处理101100遍历101100前两个字符10使count归零得到子串10。内部为空递归返回包裹后得10。继续扫描后四个字符1100count再次归零得到子串1100。内部inner 10。递归处理10得到10。包裹后得1 10 0 1100。所以101100分解为两部分[10, 1100]。排序1100 10降序排列为[1100, 10]拼接为110010。回到第一层包裹外层1和0得到1 110010 0 11100100。输出11100100与题目示例一致。示例 2s 10第一层得到一个子串10内部为空包裹后仍为10。返回10。八、总结本题巧妙地将特殊二进制串映射为括号序列利用递归分解和贪心排序的思想解决。理解“不可分子串”的判定方法计数器归零是解题的关键。通过逐层分解、内部优化、外层重排我们能够在多项式时间内求出字典序最大的字符串。这种“先分治后排序”的策略在类似嵌套结构的字符串问题中非常实用建议读者多加练习以掌握其精髓。九、参考与推广LeetCode 官方题解同类题目20. 有效的括号、22. 括号生成、32. 最长有效括号、678. 有效的括号字符串如果本文对你有帮助欢迎点赞、收藏、关注你的支持是我创作的动力