分数: 300 点
问题陈述
后藤刚刚收到一本字典。然而,他不认识字典中使用的语言。他对字典做了一些分析,发现字典里包含了所有可能的内容。 多样化 按字典顺序排列的单词。
一个词叫 多样化 当且仅当它是一个由英文小写字母组成的非空字符串,并且单词中的所有字母都不同。例如, atcoder, zscoder 和 agc 是不同的词,而 gotou 和 connect 不是不同的词。
给出一个多样化的词 S,确定之后出现的下一个单词 字典中的 S ,即字典顺序上最小的多样化单词,其字典顺序大于 S,或者确定它不存在。
让 X = x_{1}x_{2}...x_{n} 和 Y = y_{1}y_{2}...y_{m} 是两个不同的字符串。 X 按字典顺序大于 Y 当且仅当 Y 是前缀 X or x_{j} > y_{j} 其中 j 是满足以下条件的最小整数 x_{j} \neq y_{j}.
约束
- 1 \leq |S| \leq 26
- S 是一个多样化的词。
输入
输入由标准输入按以下格式给出:
S
输出
打印之后出现的下一个单词
字典中的 S ,或者 -1 如果不存在。
示例输入 1
atcoder
示例输出 1
atcoderb
atcoderb 是字典顺序上最小的多样化单词,其字典顺序大于 atcoder。请注意 atcoderb 按字典顺序小于 b.
示例输入 2
abc
示例输出 2
abcd
示例输入 3
zyxwvutsrqponmlkjihgfedcba
示例输出 3
-1
这是词典上最大的多样化单词,所以答案是 -1.
示例输入 4
abcdefghijklmnopqrstuvwzyx
示例输出 4
abcdefghijklmnopqrstuvx