String chaning

string_chaining.cpp

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
#define PR cout << 11 << endl;
using namespace std;
 
string arr[50010];
 
typedef unordered_map<string, int> Map;
 
Map memo;
Map chk;
 
// int depth=0;
 
int dfs(string s, int len) {
    // depth += 2;
    // string sp;
    // for(int i=0; i<depth; i++) {
    //     sp.push_back(' ');
    // }
    // cout << sp;
    // cout << s << " - " << len << endl;
    if(memo.find(s) != memo.end())
        return memo[s];
    int ret;
    int l=0;
    int sz = s.length();
    if(sz == 0)
        ret = 0;
    else if(sz == 1)
        ret = 1;
    else if(chk.find(s) == chk.end())
         ret = 0;
    else {
        int chain_len = -1;
        for(int i=0; i<sz; i++) {
            string tmp;
            if(i==0)
                tmp = s.substr(1, sz-1);
            else if (i==sz-1)
                tmp = s.substr(0, sz-1);
            else
                tmp = s.substr(0, i) + s.substr(i+1, sz - i - 1);
 
            chain_len = dfs(tmp, len+1);
            l = (l < chain_len ? chain_len : l);
        }
        ret = len + l;
    }
    // depth-=2;
    memo[s] = ret;
    return ret;
}
 
bool comp(string s1, string s2) {
    int l1 = s1.length();
    int l2 = s2.length();
    if(l1 < l2) return true;
    else if(l1 == l2) return s1 < s2;
    else return false;
}
 
int main() {
    int n;
    cin >> n;
    string s;
    for(int i=0; i<n ;i++) {
        cin >> s;
        arr[i] = s;
        chk[s] = 1;
    }
 
    sort(arr, arr+n, comp);
 
    cout << dfs(arr[n-1], 0) << endl;
    return 0;
}