T761.特殊的二进制字符串

dfs, divide and conquer,https://leetcode.cn/problems/special-binary-string/

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

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

给定一个特殊的二进制字符串 s。

一次移动操作包括选择字符串 s 中的两个连续的、非空的、特殊子串，并交换它们。两个字符串是连续的，如果第一个字符串的最后一个字符与第二个字符串的第一个字符的索引相差正好为 1。

返回在字符串上应用任意次操作后可能得到的字典序最大的字符串。

示例 1:

输入: S = "11011000"
输出: "11100100"
解释:
将子串 "10" （在 s[1] 出现） 和 "1100" （在 s[3] 出现）进行交换。
这是在进行若干次操作后按字典序排列最大的结果。

示例 2：

输入：s = "10"
输出："10"

提示：

1 <= s.length <= 50
s[i] 为 '0' 或 '1'。
s 是一个特殊的二进制字符串。

这个问题可以通过递归和分治的思想来解决。

题目分析

首先，我们要理解“特殊的二进制字符串”的性质。题目给出的两个定义：

0 的数量等于 1 的数量。
每一个前缀中 1 的数量大于等于 0 的数量。

这与有效括号序列（Balanced Parentheses）的定义完全一致：如果把 1 看作左括号 (，把 0 看作右括号 )，那么特殊的二进制字符串就是一个合法的括号序列。

题目允许的操作是：交换两个连续且非空的特殊子串。这实际上意味着我们可以在同一层级上对括号序列进行排序，使得最终生成的字符串字典序最大。

解题思路

拆分最小特殊子串：一个特殊的字符串 $s$ 可以拆分成若干个不可再分的最小特殊子串 $s_{1}, s_{2}, . . ., s_{k}$ 。
- 例如：110010 可以拆分为 1100 和 10。
- 拆分方法：使用一个计数器 count，遇到 1 加 1，遇到 0 减 1。当 count 回到 0 时，我们就截获了一个最小特殊子串。
递归处理内部：对于每一个最小特殊子串（形如 1...0），由于它是最小的，其首字符必为 1，末字符必为 0。中间的部分 ... 也一定是一个特殊的二进制字符串（可能为空）。为了得到字典序最大的结果，我们需要对这个中间部分递归调用 makeLargestSpecial。
排序并合并：当我们将最外层拆分出来的所有子串都经过递归处理后，得到了一个子串列表。为了让总字符串的字典序最大，我们只需要将这些处理过的子串按从大到小（降序）排列，然后拼接起来即可。

Python 代码实现

python

class Solution:
    def makeLargestSpecial(self, s: str) -> str:
        if not s:
            return ""
        
        results = []
        count = 0
        i = 0
        
        # 步骤 1 & 2: 遍历字符串，拆分出所有顶层的“最小特殊子串”
        for j, char in enumerate(s):
            if char == '1':
                count += 1
            else:
                count -= 1
            
            # 当 count 为 0 时，说明 s[i:j+1] 是一个最小特殊子串
            if count == 0:
                # 剥去首尾的 '1' 和 '0'，递归处理中间部分
                # 然后再把 '1' 和 '0' 补回来
                inner_max = self.makeLargestSpecial(s[i+1 : j])
                results.append("1" + inner_max + "0")
                # 更新下一个子串的起点
                i = j + 1
        
        # 步骤 3: 将所有处理后的子串按字典序降序排列并拼接
        results.sort(reverse=True)
        return "".join(results)

复杂度分析

时间复杂度： $O (n^{2})$ 。其中 $n$ 是字符串的长度。
- 每一层递归都会遍历字符串，最坏情况下递归深度为 $n / 2$ 。
- 排序的开销在字符串长度较短时（提示中 $n \leq 50$ ）非常小。
空间复杂度： $O (n)$ 。主要是递归调用栈的开销以及存储中间子串列表的开销。

示例模拟

以 s = "11011000" 为例：

外层拆分：整个字符串 1(101100)0 是一个最小特殊子串（因为 count 直到最后才归 0）。
进入递归处理中间部分 101100：
- 拆分为 10 和 1100。
- 递归处理 10 内部（空），结果为 10。
- 递归处理 1100 内部（10），结果为 1100。
- 得到列表 ["10", "1100"]。
- 降序排序得到 ["1100", "10"]。
- 合并得到 110010。
回到外层，补回首尾：1 + 110010 + 0 = 11100100。

T761.特殊的二进制字符串 ​

T761.特殊的二进制字符串