Hard

题目描述

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

  • 0 的数量与 1 的数量相等。
  • 在任意前缀中，1 的数量都大于或等于 0 的数量。

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

一步操作包括选择 s 的两个连续且非空的特殊子字符串，然后将它们交换。两个字符串连续是指第一个字符串的最后一个字符恰好在第二个字符串的第一个字符的前一个索引位置。

在对字符串执行上述操作后，返回字典序最大的结果字符串。

示例 1：

输入：s = "11011000"
输出："11100100"
解释：交换子字符串 "10" [出现在 s[1]] 和 "1100" [出现在 s[3]]。
这是在进行若干次交换后能够得到的字典序最大的字符串。

示例 2：

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

提示：

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

解题思路

这是一个递归分治问题。我们需要理解特殊二进制序列的本质：它们本质上是有效的括号序列，其中 1 对应左括号 (，0 对应右括号 )。

核心思路：

  1. 识别山峰（Mountains）：特殊子字符串可以看作山峰，即从起点到终点回到相同高度的路径，且中间不会低于起点。
  2. 分治策略：将字符串分解为若干个独立的山峰，每个山峰都是一个完整的特殊子字符串。
  3. 递归处理：对每个山峰内部递归求解最优排列，然后将所有山峰按字典序降序排列。
  4. 山峰合并：对于单个山峰（形如 1...0），去掉外层的 1 和 0，递归处理内部，然后重新包装。

算法步骤：

  • 遍历字符串，用计数器追踪当前的"高度"（遇到 1 加1，遇到 0 减1）
  • 当计数器回到 0 时，说明找到了一个完整的特殊子字符串
  • 将所有找到的特殊子字符串递归处理后按字典序降序排列
  • 对于每个子字符串，如果它是山峰形式，则去掉首尾的 10，递归处理中间部分

这种方法利用了贪心策略：为了获得字典序最大的结果，应该将较大的特殊子字符串放在前面。

代码实现

class Solution {
public:
    string makeLargestSpecial(string s) {
        int count = 0, start = 0;
        vector<string> mountains;
        
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '1') count++;
            else count--;
            
            if (count == 0) {
                string mountain = "1" + makeLargestSpecial(s.substr(start + 1, i - start - 1)) + "0";
                mountains.push_back(mountain);
                start = i + 1;
            }
        }
        
        sort(mountains.begin(), mountains.end(), greater<string>());
        
        string result = "";
        for (const string& mountain : mountains) {
            result += mountain;
        }
        
        return result;
    }
};

class Solution:
    def makeLargestSpecial(self, s: str) -> str:
        count = start = 0
        mountains = []
        
        for i, c in enumerate(s):
            if c == '1':
                count += 1
            else:
                count -= 1
            
            if count == 0:
                mountain = '1' + self.makeLargestSpecial(s[start + 1:i]) + '0'
                mountains.append(mountain)
                start = i + 1
        
        mountains.sort(reverse=True)
        return ''.join(mountains)

public class Solution {
    public string MakeLargestSpecial(string s) {
        int count = 0, start = 0;
        List<string> mountains = new List<string>();
        
        for (int i = 0; i < s.Length; i++) {
            if (s[i] == '1') count++;
            else count--;
            
            if (count == 0) {
                string mountain = "1" + MakeLargestSpecial(s.Substring(start + 1, i - start - 1)) + "0";
                mountains.Add(mountain);
                start = i + 1;
            }
        }
        
        mountains.Sort((a, b) => b.CompareTo(a));
        
        return string.Join("", mountains);
    }
}

var makeLargestSpecial = function(s) {
    let count = 0, start = 0;
    let mountains = [];
    
    for (let i = 0; i < s.length; i++) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n²) - 每层递归处理 O(n) 个字符，最坏情况下递归深度为 O(n)
空间复杂度O(n²) - 递归调用栈和字符串存储空间

相关题目