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。
     • 清空 s，准备处理下一个并列子串。
4. 将 q 中的字符串按照 a + b > b + a 的规则排序（即比较两种拼接方式的字典序，大的在前）。
5. 将排序后的所有字符串拼接成最终结果 res，返回。

代码实现（C++）

classSolution{public: string makeLargestSpecial(string S){if(S.size()<=2)return S;// 基础情况 vector<string> sub;// 存储一级子串 string cur;int cnt =0;for(char c : S){ cur += c;if(c =='1') cnt++;else{ cnt--;if(cnt ==0){// 找到一个一级子串// 递归处理内部（去掉首尾的1和0） string inner =makeLargestSpecial(cur.substr(1, cur.size()-2)); sub.push_back('1'+ inner +'0');// 重新包裹 cur.clear();}}}// 将一级子串按字典序最大的方式排序sort(sub.begin(), sub.end(),[](const string& a,const string& b){return a + b > b + a;});// 拼接 string ans;for(string& s : sub) ans += s;return ans;}};

代码解释

• 基础情况：当长度 ≤ 2 时，特殊串只能是 "10"（或空串），无需进一步处理。
• 计数器 cnt：用于识别一级特殊子串。当 cnt 从 0 开始，经过若干字符后再次变为 0，这一段就是一级子串。这类似于括号匹配中找到一个完整的括号对。
• 递归处理内部：一级子串去掉首尾 '1' 和 '0' 后，内部可能包含多个并列的特殊子串（例如 "1100" 去掉首尾得 "10"，"11011000" 去掉首尾得 "101100"），这些内部子串也需要达到最大字典序，所以递归调用。
• 排序规则：对于两个并列的子串 a 和 b，要使得最终拼接最大，需要比较 a+b 和 b+a 的字典序，选择更大的拼接方式。这种比较具有传递性，可以确保排序后整体最大（类似于 LeetCode 179 最大数问题）。
• 重新包裹：内部处理完后，再套上 '1' 和 '0'，这样当前层的一级子串已经内部最优。

举例演示

以 S = "11011000" 为例：

• 遍历过程：
  • 读入 1，cnt=1，cur="1"
  • 读入 1，cnt=2，cur="11"
  • 读入 0，cnt=1，cur="110"
  • 读入 1，cnt=2，cur="1101"
  • 读入 1，cnt=3，cur="11011"
  • 读入 0，cnt=2，cur="110110"
  • 读入 0，cnt=1，cur="1101100"
  • 读入 0，cnt=0，此时 cur="11011000"，是一个一级子串。
    • 内部部分：cur.substr(1, 6) = "101100"。
    • 递归处理 "101100"：
      • 遍历 "101100"：
        • 1 -> cnt=1, cur="1"
        • 0 -> cnt=0, cur="10"，找到一级子串。内部部分 "" 递归返回 ""，包裹后得 "10"，加入 sub1。
        • 继续 1 -> cnt=1, cur="1"
        • 1 -> cnt=2, cur="11"
        • 0 -> cnt=1, cur="110"
        • 0 -> cnt=0, cur="1100"，找到一级子串。内部部分 "10" 递归返回 "10"（因为长度 2），包裹后得 "1100"，加入 sub1。
      • sub1 = ["10","1100"]。排序比较：
        • "10"+"1100" = "101100"，"1100"+"10" = "110010"，"110010" 更大，所以排序后为 ["1100","10"]。
      • 递归返回 "110010"。
    • 外层包裹 '1' + "110010" + '0' 得 "11100100"。
    • 将 "11100100" 加入 sub（此时只有这一个子串）。
• 排序（只有一个）后直接拼接，结果为 "11100100"。

通过手动验证，"11011000" 的最大特殊串确实是 "11100100"。

复杂度分析

• 时间复杂度：每个字符在递归的每一层都会被访问一次，递归深度为特殊串的嵌套层数，最坏情况下为 O(n)。排序操作在最坏情况下，每一层可能需要排序，总时间复杂度约为 O(n log n)。实际上，由于递归和排序的综合，整体时间复杂度为 O(n²) ？更精确的分析：每个字符被处理多次，但每次递归都会减少问题规模，排序的字符串总长度和为 n，每次排序的复杂度与字符串长度相关。可以粗略估计为 O(n²) 但在数据范围内足够。LeetCode 官方题解给出的是 O(n²) 级别。
• 空间复杂度：递归调用栈深度 O(n)，加上存储临时字符串，总空间复杂度 O(n)。

总结

• 本题的关键在于将特殊串与括号序列联系起来，利用计数器分解出并列的子串。
• 递归处理内部，保证子问题最优。
• 排序规则 a+b > b+a 巧妙地解决了并列子串的排列问题，使得最终字典序最大。
• 该解法既清晰又高效，是处理此类问题的经典思路。