String Reorder

题目描述

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

输入格式

唯一一行包含一个长度为 n 的字符串，字符串由字符 A–Z 组成。

输出格式

输出字典序最小的重新排列后的字符串，要求没有两个相邻的字符相同。如果无法构造这样的字符串，则输出 -1。

HATTIVATTI

AHATITITVT

提示

$1 \le n \le 10^6$

标签: CSES1743|入门题

来源

CSES1743|入门题