TopCoder SRM 735 Div1 Easy PalindromeSubsequence

気づけばあっさりな問題。
http://community.topcoder.com/stat?c=problem_statement&pm=14925

問題

abだけで構成された文字列Sが与えられる。
このSをいくつかの(非連続でもよい)部分文字列に分割することを考える。
その際、各部分文字列が回文であるもののうち、部分文字列数が最小のものを１つ示せ。

解法

実はこの問題、最大でも部分文字列数は2で済む。
文字の種類が2つなので、"a"と"b"をそれぞれ集めれば勝手に回文になるためである。

よって、もともとSが回文なら全体で1個の文字列、そうでなければ"a""b"を集めたものを回答するだけ。

class PalindromeSubsequence {
	public:
	vector <int> optimalPartition(string s) {
		int i;
		vector<int> R(s.size(),1);
		FOR(i,s.size()) if(s[i]!=s[s.size()-1-i]) break;
		if(i==s.size()) return R;
		FOR(i,s.size()) R[i]+=s[i]=='b';
		return R;
	}
}

まとめ

気づくまでちょっとかかった。