问题 5635 --最小字符串

5635: 最小字符串★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 46  解决: 13
[提交][状态][命题人:]

题目描述

给你一个三元字符串(它是一个只包含字符'0''1''2'的字符串)

您可以交换任意两个相邻(连续)字符“0”“1”(即将“01”替换为“10”或反之亦然)或任意两个相邻(连续)字符“1”“2”(即将“12”替换为“21”或反之亦然)

例如,对于字符串"010210",我们可以执行以下操作:

010210”→“100210”;

010210”→“001210”;

010210”→“010120”;

010210010201”。

请注意,您不能交换“02”→“20”,反之亦然。除了上面描述的操作之外,您不能对给定的字符串执行任何其他操作。

您的任务是通过使用这些交换任意次数(可能为零次)来获得尽可能小的(按字典顺序)字符串。

     规定:对于两个长度相等的字符串a和字符串b而言,如果存在某个位置i(1≤i≤|a|,其中|s|是字符串s的长度),使得对于每一个j<i都有aj=bj,并且ai<bi,则说明字符串a小于字符串b(按字典顺序)。

输入

    一行一个字符串ss仅由'0''1''2'组成,长度在1105()之间(1<=|s|<=105)。

输出

     一行一个字符串:通过使用上述的交换操作任意次数(可能为0)可以获得的最小字符串 (按字典顺序)
样例输入
Copy
100210
样例输出
Copy
001120

提示

样例2输入:
11222121
样例2输出:
11112222


样例3输入:
20
样例3输出:
20



来源

 

[提交][状态]