IdealString
#include <string>
#include <numeric>
using namespace std;
class IdealString
{
string BT( int length, string w );
public:
string construct( int length );
};
string IdealString::construct( int length )
{
return BT( length, "" );
}
string IdealString::BT( int length, string w )
{
int index[26] = { 0 };
int number[26] = { 0 };
for ( int i=0; i<(int)w.length(); i++ )
{
if ( index[w[i]-'A'] == 0 )
index[w[i]-'A'] = i + 1;
number[w[i]-'A']++;
}
if ( accumulate( index, index+26, 0 ) > length )
return "";
if ( (int)w.size() >= length )
return w;
int i;
for ( i=0; i<26; i++ )
if ( number[i] < index[i] )
break;
if ( i < 26 )
{
string r = BT( length, w + (char)('A'+i) );
if ( r != "" )
return r;
}
for ( i=0; i<26; i++ )
if ( index[i] == 0 )
break;
if ( i < 26 )
{
string r = BT( length, w + (char)('A'+i) );
if ( r != "" )
return r;
}
return "";
}