登录【宫水三叶】经典构造题
构造
我们可以定义每个字符的得分：字符 1 得分为 $1$ 分，字符 0 得分为 $-1$ 分。
根据题目对「特殊字符串」的定义可知，给定字符串 s 的总得分为 $0$，且任意前缀串不会出现得分为负数的情况。
考虑将 s 进行划分为多个足够小特殊字符串 item（足够小的含义为每个 item 无法再进行划分），每个 item 的总得分为 $0$。根据 s 定义，必然可恰好划分为多个 item。
每次操作可以将相邻特殊字符串进行交换，于是问题转换为将 s 进行重排，求其重排后字典序最大的方案。
首先可以证明一个合法 item 必然满足 1...0 的形式，可通过「反证法」进行进行证明：定义了 item 总得分为 $0$，且长度不为 $0$，因此必然有 1 有 0。若第一位字符为 0，则必然能够从第一位字符作为起点，找到一个得分为负数的子串，这与 s 本身的定义冲突（s 中不存在得分为负数的前缀串）；若最后一位为 1，根据 item 总得分为 $0$，可知当前 item 去掉最后一位后得分为负，也与 s 本身定义冲突（s 中不存在得分为负数的前缀串）。
因此可将构造分两步进行：
- 对于每个
item进行重排，使其调整为字典序最大 - 对于
item之间的位置进行重排，使其整体字典序最大
由于题目没有规定重排后的性质，为第一步调整和第二步调整的保持相对独立，我们只能对 item 中的 1...0 中的非边缘部分进行调整（递归处理子串部分）。
假设所有 item 均被处理后，考虑如何进行重排能够使得最终方案字典序最大。
若有两个 item，分别为 a 和 b，我们可以根据拼接结果 ab 和 ba 的字典序大小来决定将谁放在前面。
这样根据「排序比较逻辑」需要证明在集合上具有「全序关系」:
我们使用符号 $@$ 来代指我们的「排序」逻辑：
- 如果 $a$ 必须排在 $b$ 的前面，我们记作 $a @ b$；
- 如果 $a$ 必须排在 $b$ 的后面，我们记作 $b @ a$；
- 如果 $a$ 既可以排在 $b$ 的前面，也可以排在 $b$ 的后面，我们记作 $a#b$；
2.1 完全性
具有完全性是指从集合 items 中任意取出两个元素 $a$ 和 $b$，必然满足 $a @ b$、$b @ a$ 和 $a#b$ 三者之一。
这点其实不需要额外证明，因为由 $a$ 和 $b$ 拼接的字符串 $ab$ 和 $ba$ 所在「字典序大小关系中」要么完全相等，要么具有明确的字典序大小关系，导致 $a$ 必须排在前面或者后面。
2.2 反对称性
具有反对称性是指由 $a@b$ 和 $b@a$ 能够推导出 $a#b$。
$a@b$ 说明字符串 $ab$ 的字典序大小数值要比字符串 $ba$ 字典序大小数值大。
$b@a$ 说明字符串 $ab$ 的字典序大小数值要比字符串 $ba$ 字典序大小数值小。
这样，基于「字典序本身满足全序关系」和「数学上的 $a \geqslant b$ 和 $a \leqslant b$ 可推导出 $a = b$」。
得证 $a@b$ 和 $b@a$ 能够推导出 $a#b$。
2.3 传递性
具有传递性是指由 $a@b$ 和 $b@c$ 能够推导出 $a@c$。
我们可以利用「两个等长的拼接字符串，字典序大小关系与数值大小关系一致」这一性质来证明，因为字符串 $ac$ 和 $ca$ 必然是等长的。
接下来，让我们从「自定义排序逻辑」出发，换个思路来证明 $a@c$：
然后我们只需要证明在不同的 $i$ $j$ 关系之间（共三种情况），$a@c$ 恒成立即可：
- 当 $i == j$ 的时候：
- 当 $i > j$ 的时候：
- 当 $i < j$ 的时候：
综上，我们证明了无论在何种情况下，只要有 $a@b$ 和 $b@c$ 的话，那么 $a@c$ 恒成立。
我们之所以能这样证明「传递性」，本质是利用了自定义排序逻辑中「对于确定任意元素 $a$ 和 $b$ 之间的排序关系只依赖于 $a$ 和 $b$ 的第一个不同元素之间的大小关系」这一性质。
最终，我们证明了该「排序比较逻辑」必然能排序出字典序最大的方案。
代码：
###Java
class Solution {
public String makeLargestSpecial(String s) {
if (s.length() == 0) return s;
List<String> list = new ArrayList<>();
char[] cs = s.toCharArray();
for (int i = 0, j = 0, k = 0; i < cs.length; i++) {
k += cs[i] == '1' ? 1 : -1;
if (k == 0) {
list.add("1" + makeLargestSpecial(s.substring(j + 1, i)) + "0");
j = i + 1;
}
}
Collections.sort(list, (a, b)->(b + a).compareTo(a + b));
StringBuilder sb = new StringBuilder();
for (String str : list) sb.append(str);
return sb.toString();
}
}
###TypeScript
function makeLargestSpecial(s: string): string {
const list = new Array<string>()
for (let i = 0, j = 0, k = 0; i < s.length; i++) {
k += s[i] == '1' ? 1 : -1
if (k == 0) {
list.push('1' + makeLargestSpecial(s.substring(j + 1, i)) + '0')
j = i + 1
}
}
list.sort((a, b)=>(b + a).localeCompare(a + b));
return [...list].join("")
};
- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(n)$
最后
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/
也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
