Codeforces #170, Division 2, B : New Problem

問題文

http://codeforces.com/contest/278/problem/B

概要

英小文字からなる n 個の文字列が与えられる。
これらの文字列の部分文字列でないような最短の文字列を求めよ。
答えが複数存在する場合は辞書式順序で最小となるものを出力せよ。

解法

制約より、与えられる文字列の長さは高々 600 文字です。
これに対し、英小文字二文字からなる文字列は 通りあります。
つまり、与えられた文字列では二文字の列を網羅できません。
従って、答えは高々二文字となるので全探索が可能です。

コード

typedef vector<string> VS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define ALL( c ) (c).begin(), (c).end()
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

string solve1( VS titles )
{
	set<char> chars;
	FOR( t, titles )
	{
		chars.insert( ALL( t ) );
	}
	
	for ( char c = 'a'; c <= 'z'; c++ )
	{
		if ( !EXIST( chars, c ) )
		{
			return string() + c;
		}
	}

	return "";
}

string solve2( VS titles )
{
	set<string> substrs;
	FOR( t, titles )
	{
		REP( i, 0, t.size() - 1 )
		{
			substrs.insert( t.substr( i, 2 ) );
		}
	}

	for ( char c1 = 'a'; c1 <= 'z'; c1++ )
	{
		for ( char c2 = 'a'; c2 <= 'z'; c2++ )
		{
			if ( !EXIST( substrs, string() + c1 + c2 ) )
			{
				return string() + c1 + c2;
			}
		}
	}

	return "";
}

string solve( VS titles )
{
	string res = solve1( titles );
	
	if ( res != "" )
	{
		return res;
	}

	return solve2( titles );
}

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	VS titles( n );
	FOR( t, titles )
	{
		cin >> t;
	}

	cout << solve( titles ) << endl;

	return 0;
}