A: Diverse Word - AtCoder Grand Contest 022

入力に応じて3種類に場合分けする この3種は入出力例で示されているのでそれを使って説明する。

1) |S| < 26のとき

使われていない文字で最小の文字を末尾に追加する。 入力例1のatcoder ではbが使われていないので末尾にbをつけて atcoderbが解となる。 入力例2のabc ではdが使われていないので末尾にdをつけてabcdが解となる。

2) S = "zyxwvutsrqponmlkjihgfedcba"のとき

入力例3は辞書順最大なのでどうしようもない。

3) それ以外の場合(|S|=26)

next_permutationを使って次の順列を求める。そしてその接頭辞で 条件を満たすものが解。

入力例4 abcdefghijklmnopqrstuvwzyxにnext_permutationを使うと abcdefghijklmnopqrstuvxwyzとなる。 この2つの文字列を比較すると

abcdefghijklmnopqrstuvwzyx
abcdefghijklmnopqrstuvxwyz
                      *

上の印をつけた部分が最初に異なる部分である。つまり、ここまで 含めた接頭辞で初めて元の文字列より辞書順が後になる。したがって abcdefghijklmnopqrstuvxが解となる。

string S;
cin >> S;
vector<bool> F(128);

int N = sz(S);
int A = 0;
rep(i, N - 1)A |= S[i] < S[i + 1];

if (N == 26) {
    if(!A)cout << -1 << endl;
    else {
        string T = S;
        next_permutation(all(S));
        rep(i, N) {
            cout << S[i];
            if (S[i] != T[i])break;
        }
        cout << endl;
    }
} else {
    rep(i, N) {
        F[S[i]] = 1;
    }
    for (char c = 'a'; c <= 'z'; ++c)if (!F[c]) {
        S += c;
        cout << S << endl;
        break;
    }
}