はまやんはまやんはまやん

hamayanhamayan's blog

String Transformation [Educational Codeforces Round 39 C]

http://codeforces.com/contest/946/problem/C

文字列Sがある。
これに以下の操作を行って、部分列に「abcdefghijklmnopqrstuvwxyz」を含むように出来るか。出来るなら、変換後の文字列を答えよ。
操作「文字毎にインクリメントする('z'は変換できない)」

解法

http://codeforces.com/contest/946/submission/36152953

貪欲に変換していこう。
先頭から順番にabc...を作っていく。
これでa~zを作れればそれを答える。

string S;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;

    char pre = 'a';
    fore(c, S) if(pre <= 'z') if (c <= pre) c = pre, pre++;

    if (pre <= 'z') printf("-1\n");
    else printf("%s\n", S.c_str());
}