SRM563 Div1 Easy - FoxAndHandle

問題

長さn(:偶数)の文字列sが与えられる
sを2つの文字列x,yに分け、yがxのアナグラムになっているようにしたい
xとしてあり得る文字列のうち辞書順最小のものを求めよ

2 <= n <= 50
xとしてあり得る文字列が少なくとも1つは存在することが保証される

解法

1文字ずつ決めていく
今の仮の答えである文字列の各文字をsのなるべく左に対応させてみて、左からsを見た時にそれらが全て登場するまでにある文字が (sで登場する回数)/2+1 回以上登場したらダメ
(そうなった場合答えの残りの文字を決めきれない)
そうでなければok

↑史上最高にわかりにくい説明
コード↓の方がまだわかりやすいと思う

class FoxAndHandle {
public:
	string lexSmallestName(string s) {
		int n = s.size(), a[26] = {};
		each(i,s) a[i-'a']++;
		rep(i,26) a[i] /= 2;
		string res;
		rep(m,n/2) rep(c,26){
			res.push_back('a'+c);
			int ok = 1, x[26] = {}, y[26] = {}, id = 0;
			rep(i,n) {
				if (s[i]==res[id]) {
					if (++x[s[i]-'a']>a[s[i]-'a']) ok = 0;
					if (++id==res.size()) break;
				} else if (++y[s[i]-'a']>a[s[i]-'a']) ok = 0;
			}
			if (ok) break;
			res.pop_back();
		}
		return res;
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=12331&rd=15185