#1795. 重排

    ID: 1795 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>CTT赛事:contest1421来源:qoj.ac数据:公开样例字符串

重排

重排

题目描述

标题: 重排 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

定义一个字符串是好串,当且仅当它本身是它的最小表示,即字符串 s=s1s2⋯sn 是好串当且仅当 ∀2≤i≤n,字符串 t=sisi+1si+2⋯sns1s2⋯si−1 的字典序不小于 s。

给定一个仅有小写字母组成的字符串 S,将 S 中的字母重新排列成一个好的字符串,并最大化这个字符串的字典序。输出重排后的字符串。

输入格式

输入一行一个字符串 S。

输出格式

输出一行一个字符串,表示答案。

样例数据

样例 1输入

acbca

样例 1 输出

acacb

样例 2 输入

cadcbaadcbadbacdb

样例 2 输出

accccbbbbadadadad

数据范围与提示

对于所有数据,保证 1≤|S|≤106。每个子任务的特殊限制如下:

Sub 1(10分):|S|≤10;

Sub 2(20分):|S|≤50,Si∈{a,b,c};

Sub 3(30分):|S|≤1000;

Sub 4(40分):无特殊限制。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

acbca
acacb

样例 2

cadcbaadcbadbacdb
accccbbbbadadadad