ConvertibleStrings.cpp

#include <iostream>
#include <string>
#include <array>
#include <algorithm>

using namespace std;

constexpr char CHARS[] = "ABCDEFGHI";

using Perm = array<int, sizeof(CHARS)-1>;

int n_unmatch(const string& stra, const string& strb)
{
    int n = 0;
    for(unsigned int i = 0; i < stra.size(); ++i){
        if(stra[i] != strb[i]) ++n;
    }
    return n;
}

string trans(const string& str, const Perm perm)
{
    string ret(str.size(), 0);
    for(unsigned int i = 0; i < str.size(); ++i){
        ret[i] = CHARS[perm[str[i]-'A']];
    }
    return ret;
}

class ConvertibleStrings{
public:
    int leastRemovals(const string& A, const string& B)
    {
        int r_min = 99999;

        int n = 0;
        Perm perm{ 0, 1, 2, 3, 4, 5, 6, 7, 8 };
        do{
            ++n;
            int r = n_unmatch(trans(A,perm), B);
            if(r < r_min)
                r_min = r;
        } while(next_permutation(perm.begin(), perm.end()));
        //cout << n << "\n";

        return r_min;
    }
};

void test(const string& stra, const string& strb)
{
    ConvertibleStrings cs;
    cout << cs.leastRemovals(stra, strb) << "\n";
}

#if 0
int main()
{
    test("DD", "FF");
    test("AAAA", "ABCD");
    test("AAIAIA", "BCDBEE");
    test("ABACDCECDCDAAABBFBEHBDFDDHHD", "GBGCDCECDCHAAIBBFHEBBDFHHHHE");

    test("ABC", "DDD");
    test("", "");

    return 0;
}
#endif