#CS1743. 字符串重排

字符串重排

题目背景

翻译自 CSES-1743 题。

题目描述

给定一个字符串，你需要重新排列它的字符，使得相邻的字符不相同。求这样的字符串中字典序最小的排列。

输入格式

唯一的输入行是一个长度为$n$的字符串，字符串由大写字母 A–Z 组成。

输出格式

输出一个字典序最小的重排字符串，使得相邻的字符不相同。如果无法生成这样的字符串，输出 $−1$。

样例

HATTIVATTI

AHATITITVT

说明/提示

$1≤n≤10^6$。