TopCoder SRM 589, Division 2, Level 1 : GooseTattarrattatDiv2

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12733&rd=15701

概要

文字列 S が与えられる。
次の操作を繰り返して、S が単一の文字から成るようにしたい。

• アルファベットを一つ選び、その文字を全て任意の一文字に置き換える

操作には、対象になる文字一つあたり 1 の時間がかかる。

S が単一文字から成るようにするために必要な時間の最小値を求めよ。

解法

最も数の多い文字をそのまま残すようにすると、必要な時間を最小化できます。
最も多く含まれる文字の数を strlen( S ) から引くことで答えが得られます。

コード

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

class GooseTattarrattatDiv2
{
public:
	int getmin( string S )
	{
		int max = 0;
		for ( char c = 'a'; c <= 'z'; c++ )
		{
			max = std::max( max, (int)count( ALL( S ), c ) );
		}
		return S.size() - max;
	}
};