字符串重排 (Task 1743)

• 链接: https://cses.fi/problemset/task/1743
• 板块: Introductory Problems
• 时限: 1.00 s ｜ 内存: 512 MB

描述

你的任务是重排一个字符串的字符，使得没有任何两个相邻字符相同。这样的字符串中，字典序最小的是哪一个？

输入

输入仅一行，包含一个由 A–Z 组成、长度为 $n$ 的字符串。

输出

打印字典序最小、且相邻字符互不相同的重排字符串。如果无法构造出这样的字符串，则打印 $-1$。

约束

• $1 \le n \le 10^6$

样例

输入：
AABBA
输出：
ABABA

注：该题样例在抓取通道中被截断，以上样例依据 CSES 公开题面补全。

来源：CSES Problem Set（英文原文，LaTeX 公式以源码保留）。隐藏测试用例不公开，仅含页面展示的样例 I/O。