Here is code:
Code
#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
#define IOS \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
//#define int long long
int k;
vector<string> s;
map<vector<int>, int> dp;
int rec(vector<int> levelVector) {
//base case
for (int i = 0; i < k; ++i) {
if (levelVector[i] == s[i].length()) {
return 0;
}
}
//cache check
// if(dp[l1][l2]!=-1) return dp[l1][l2];
if (dp.find(levelVector) != dp.end()) {
return dp[levelVector];
}
//transition
int ans = 0;
set<char> st;
for (int i = 0; i < k; ++i) {
st.insert(s[i][levelVector[i]]); //ith strings ith level
if (st.size() > 1) break;
}
if (st.size() == 1) {
vector<int> temp = levelVector;
for (int i = 0; i < k; ++i) {
temp[i]++; // l1 + 1 , l2 + 1, l3 + 1, ...
}
ans = max(ans, 1 + rec(temp)); // ans=1+rec(l1+1,l2+1)
}
for (int i = 0; i < k; ++i) {
vector<int> temp1 = levelVector;
temp1[i]++; // l1 + 1 or l2 + 1
ans = max(ans, rec(temp1));
temp1[i]--; // get back to original
}
//save and return
return dp[levelVector] = ans;
}
void solve() {
cin >> k;
s.resize(k);
for (int i = 0; i < k; ++i) {
cin >> s[i];
}
vector<int> temp(k,0);
cout<<rec(temp)<<endl;
}
signed main() {
#ifndef ONLINE_JUDGE
freopen("Input.txt", "r", stdin);
freopen("Output.txt", "w", stdout);
freopen("Error.txt", "w", stderr);
#endif
auto start1 = high_resolution_clock::now();
IOS
solve();
auto stop1 = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop1 - start1);
#ifndef ONLINE_JUDGE
cerr << "Time: " << duration.count() / 1000 << endl;
#endif
return 0;
}
//input
//5
//abcd
//bcde
//cdea
//abbcde
//aacdeabc
//output
//2
let max string length = s no of strings = k Time complexity= o((k^2)*(s^k)*log(s))