TopCoder, Single Round Match 656, Division 2, Level 1 : CorruptedMessage

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13748&rd=16416

問題概要

　英小文字の内 1 種類の文字からなる文字列 を送ったが，伝送途中で丁度 文字が異なる文字に変わってしまった． と が与えられるので，元の文字列として考えられるものを 1 つ復元せよ．1 つ以上存在することは保証される．
　

解法

　 とします．
　元の文字列として考えられるのは，1 種類の文字からなる 文字の文字列です．これは 26 種類しか無いので，簡単に列挙できます．26 種類の候補それぞれに対して妥当性の判定をすることができれば，答えを探すことができます．
　1 種類の文字からなる文字列 ( ) をもってきたとき， が元の文字列で有り得る場合とは，題意より， から丁度 文字を変更することで にできる場合です． が 1 種の文字 からなることを考えると， に含まれる， ではない文字の個数が に等しい場合であると言えます．言い換えると， に含まれる の個数を から引いた値が に等しければ，その文字列は元の文字列として妥当なものであると分かります．このことを調べるためには，各文字が に含まれる個数だけが分かれば十分で，これは予め数えておくことができます．
　 に各文字が含まれる個数を調べることは，文字列を 1 回走査すればできるので， 時間です．調べなければならない文字列は高々定数個であり，それぞれの文字列に対する妥当性判定も定数時間なので，この部分は 時間です．また，return する文字列を生成するところで 時間かかります．従って，処理の全体は 時間で完了します．

コード

using VI = vector< int >;

#define ALL( c ) ( c ).begin(), ( c ).end()

#define SZ( v ) ( (int)( v ).size() )

class CorruptedMessage
{
public:
	string reconstructMessage( string s, int k )
	{
		int L = SZ( s );

		VI counts( 26 );
		for_each( ALL( s ), [&]( const char c ){ ++counts[ c - 'a' ]; } );

		for ( char c = 'a'; c <= 'z'; ++c )
		{
			if ( L - counts[ c - 'a' ] == k )
			{
				return string( L, c );
			}
		}
		return "";
	}
};