SRM405 Div2 Hard(1000) IdealString

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 "";
}