AGC022A Diverse Word

A - Diverse Word

提出AC
Submission #8518596 - AtCoder Grand Contest 022

int main()
{
	cout <<setprecision(10);
	string s;
	cin >> s;
 
	map<char,int> alphabet;
	rep(i,s.size()){
		char c = s[i];
		alphabet[c] = 1;
	}
	int n = alphabet.size();
	if(n==26){
		if(s=="zyxwvutsrqponmlkjihgfedcba"){
			cout << -1 << endl;
			return 0 ;
		}else{
			string sbef = s;
			next_permutation(s.begin(),s.end());
			rep(i,26){
				if(s[i]==sbef[i]){
					cout<<s[i];
				}else{
					cout<<s[i]<<endl;
					return 0;
				}
			}
		}
 
	}
	else{//多分完成
		rep(i,26){
			char c = 'a'+i;
			if(! alphabet.count(c)){
				cout << s + c << endl;
				return 0;
			}
		}
	}
	cout << -1 << endl;
}

解法・考察
アルファベットは26文字、
入力で与えられた文字列が25文字以下のときは、
与えられた文字列+ ( a ~ zで入力に存在しない文字の最小の文字）
neko が入力で与えられていたら、abcdfghijlmpqrstuvwxyzが
存在しない文字の一覧だけど、その中で最小（辞書順）のものはa なので
nekoa を出力すればいい

ここで、なんか辞書順とかうがあってなっちゃうので
アルファベットが3文字しか存在しない世界を考える

まあ、こんな感じで、
あるいふぁべっとが3文字しか存在しない世界で与えられる入力として考えられるものは
a
b
c
ab
ac
ba
bc
ca
cb
abc
acb
bac
bca
cab
cba
の15通りが考えられる。

ちなみにこの15通りっていうのはどうやって計算したらいいんですか（誰か教えてください）

この時、いい順番（察して）に並び替えると
a
ab
abc
ac
acb

b
ba
bac
bc
bca

c
ca
cab
cb
cba

• 1

このようになる。
これは a が入力出来たら abを abが来たら abc

abc が来たらacを出力する。みたいなノリになっている

で、文字数が2以下のときは存在しないなかで最小のものを付け加えればいいので
文字数が3のときを考える

abcならacとなっているが
辞書順で
abcの次のものは
acbである。出力するのは
ac

acb の辞書順の次は
bac出力は
b

bacの次は
bca出力は
bc

こんな感じになってて、あることに気づく
辞書順で次のやつを求めて、それと文字列sを比較して違う文字が出てきたところまで出力すれば答えじゃん。

ということで辞書順で次のを求めたかったらnext_permutation が使えます。

入力が "cba"のときだけ例外として-1を出力すれば勝てる
この、if"cba"
を手入力でやってるの最高にダサいけどまあいいや。