【LetMeFly】761.特殊的二进制字符串分治左右括号对移动力扣题目链接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 50s[i]为0或1。s是一个特殊的二进制字符串。解题方法分治例如示例一11011000可以看成(()(()))。我们要做的就是保持括号处于匹配状态下让对应的01字符串字典序尽可能大。匹配字符串有两种组合方式拼接如() (()) ()(())嵌套在()(())外面套一个括号变成(()(()))。这解法不就来了我们可以反其道而行之把(()(()))拆成( () (()) )对于最外层括号里的()和(())当然是(())放到()前面比较好1100放到10前面字典序更大这不就是天然的递归么(()(()))只有一个“拼接的括号”外层总体顺序不变内层()(())递归内层()(())有两个“拼接的括号”两个拼接的括号分别递归直到递归字符串为空递归停止并将两个递归完成的“拼接括号”排序重新拼接到一起变成(())()。时间复杂度O ( n 2 log n ) O(n^2\log n)O(n2logn)递归像树一样每次执行有一个排序和字符串拼接(()(())) | ()(()) / \ ()空间复杂度O ( n ) O(n)O(n)AC代码C/* * LastEditTime: 2026-02-20 11:21:04 *//* 11011000 (()(())) ( () (()) ) */classSolution{private:vectorpairint,intsplit(strings){vectorpairint,intans;intdiff0,from0;for(inti0;is.size();i){if(s[i]1){diff;}else{diff--;}if(!diff){ans.push_back({from,i});fromi1;}}returnans;}public:stringmakeLargestSpecial(string s){if(s.empty()){returns;}vectorpairint,intpairssplit(s);vectorstringparts;parts.reserve(pairs.size());for(auto[l,r]:pairs){parts.push_back(1makeLargestSpecial(s.substr(l1,r-l-1))0);}sort(parts.begin(),parts.end(),greater());string ans;for(stringpart:parts){anspart;}returnans;}};同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源