#CS1743. 字符串重排

字符串重排

题目背景

翻译自 CSES-1743 题。

题目描述

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

输入格式

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

输出格式

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

样例

HATTIVATTI

AHATITITVT

说明/提示

1≤n≤106。