Here is the problem link: Problem Link: Minimum Cost to Convert String II

Here, I treated each string in the original and changed vectors as unique graph nodes. This involved computing the hash value for every string and subsequently compressing these values. Then I used Floyd-Warshall algorithm to facilitate the establishment of connections between these compressed nodes.

Since, the combined number of unique strings in the original and changed vectors would not exceed 200. We can easily apply Floyd-Warshall.

Now, having precomputed hash values for both the source and target strings, I can easily find the hash value of any substring in constant time, as it is a crucial step during dynamic programming (DP) transitions. The time complexity in the DP phase is O (string. length^2). Overall, our time complexity can reach a maximum of N^2*logN, comfortably below the given time limit.

Why am I still getting TLE?

MY CODE:

map<int,int>comp;
vector<vector<ll>>dist;
const static int N= 1001;
int powers[N];
int invPowers[N];

int n;
const ll INF= 1e13;
vector<ll>dp;

const int mod= 1e9+9;
const int pr= 29;

int binExp(int a, int b, int mod){
int ans=1;
while(b>0){
    if(b&1ll)ans=(ans*1ll*a)%mod;
    a=(a*1ll*a)%mod;
    b>>=1ll;
}
return ans;
}
void precompute(){
    powers[0]=1;
    powers[1]=pr;
    for(int i=1;i<N; i++)powers[i]= (pr*1ll*powers[i-1])%mod;
    invPowers[0]=1;
    for(int i=1; i<N; i++)invPowers[i]= binExp(powers[i], mod-2,mod);
}
void rollingHash(string &s, vector<int>&hashS){
    int sz= s.size();
    for(int  i=0; i<sz; i++){
        int hash= (powers[i]*1ll*(s[i]-'a'+1))%mod;
        hashS.push_back(hash);
    }
    for(int i=1; i<sz; i++)hashS[i]= (hashS[i]+hashS[i-1])%mod;
}
ll findSubstringHash(int &i, int &j, vector<int>&hashArr){
    ll inv= invPowers[i];
    ll val= (hashArr[j]-(i==0?0:hashArr[i-1]));
    if(val<0)val+= mod;
    val=(val*inv)%mod;

    return val;
}

ll f(int i, string &s, string &t, vector<int>&hashS, vector<int>&hashT){
    if(i>=n)return 0;

    if(dp[i]!=-1)return dp[i];
    ll ans= INF;

    for(int j=i; j<n; j++){
        int hash1= findSubstringHash(i,j,hashS);
        int hash2= findSubstringHash(i,j,hashT);
        if(hash1==hash2)ans=min(ans, f(j+1,s,t,hashS,hashT));
        else if(comp.find(hash1)!=comp.end() && comp.find(hash2)!=comp.end()){
            int i1= comp[hash1], j1= comp[hash2];
            ans=min(ans, dist[i1][j1]+ f(j+1,s,t,hashS,hashT));
        }    
    }

    return dp[i]= ans;
}

long long minimumCost(string s, string t, vector<string>& org, vector<string>& ch, vector<int>& cost) {
    int sz= org.size();
    vector<int>hashS, hashT;
    precompute();
    rollingHash(s,hashS);
    rollingHash(t,hashT);
    vector<int>storeHashes1, storeHashes2;
    for(int i=0; i<sz; i++){
        vector<int>a,b;
        rollingHash(org[i],a);
        rollingHash(ch[i],b);
        storeHashes1.push_back(a.back());
        storeHashes2.push_back(b.back());
        comp[a.back()];
        comp[b.back()];
    }

    int ptr=0;
    for(auto &ele: comp)ele.second=ptr++;

    dist.resize(ptr,vector<ll>(ptr,INF));

    for(int i=0; i<ptr; i++)dist[i][i]=0;


    for(int i=0; i<sz; i++){

        int i1= comp[storeHashes1[i]];
        int j1= comp[storeHashes2[i]];

        if(dist[i1][j1]>cost[i])
        dist[i1][j1]= cost[i];
    }

   //10^6
    for(int k=0; k<ptr; k++){
        for(int i=0; i<ptr; i++){
            for(int j=0; j<ptr; j++){
                if((dist[i][k]!=INF && dist[k][j]!=INF) && dist[i][j]>dist[i][k]+dist[k][j]) dist[i][j]= dist[i][k]+dist[k][j];
            }
        }
    }

    n=s.size();

    dp.resize(n+1,-1);
    ll ans= f(0,s,t,hashS,hashT);

    if(ans>=INF)return -1;
    return ans;

}