These are the approaches that i have tried but getting TLE 1. Use a 3d array and continue just like we do LCS of two strings. Complexity = O(n^3). 2. First take the first two strings, find the length of LCS, then recover all the LCS of these two strings using backtracking on the DP array of these two strings. Then use these recovered LCS and find the LCS length of these strings with the last string that was given to us, and take the max len of these LCS's as the answer. Complexity = O(n^2) + complexity of recovering all the LCS strings of the first two strings

This is the link to the question ---> https://www.codingninjas.com/codestudio/problems/lcs-of-3-strings_842499?topList=top-fintech-software-engineer-interview-questions&leftPanelTab=0

Can anyone suggest a more efficient method to do this question.

This is the code for second method. ~~~~~ VVI lcs(string a, string b){ int n1=a.length(), n2 = b.length();

VVI dp(n1+1, VI (n2+1, 0));
for(int i=1;i<=n1;i++){
    for(int j=1;j<=n2;j++){
       if(a[i-1] == b[j-1]){
         dp[i][j] = 1 + dp[i-1][j-1];
       }
       dp[i][j] = max(dp[i-1][j], max(dp[i][j], dp[i][j-1]));
       //cout<<dp[i][j]<<" ";
    }
    //cout<<endl;

}
return dp;

}

string recoverLCS(string a, string b, VVI &dp, int i, int j){ //int n1 = a.length(), n2 = b.length();

if(i == 0 || j == 0) return "";

if(a[i-1] == b[j-1]){
    return a[i-1] + recoverLCS(a, b, dp, i-1, j-1);
}
if(dp[i-1][j] > dp[i][j-1]) return recoverLCS(a, b, dp, i-1, j);
return recoverLCS(a, b, dp, i, j-1);

}

vector recoverAllLCS(string a, string b, VVI &dp, int i, int j){ if(i == 0 || j == 0) return {""};

if(a[i-1] == b[j-1]){
    vector<string> temp = recoverAllLCS(a, b, dp, i-1, j-1);

    for(int z=0;z<(int)temp.size();z++){
       temp[z] = a[i-1] + temp[z];
    }
    // for(auto x: temp){
    //     x = a[i-1]  + x;     
    // }

    return temp;
}
else if(dp[i-1][j] > dp[i][j-1]){
    return recoverAllLCS(a, b, dp, i-1, j);
}
else if(dp[i-1][j] < dp[i][j-1]){
    return recoverAllLCS(a, b, dp, i, j-1);
}
else{
    vector<string> vs1 = recoverAllLCS(a, b, dp, i-1, j);
    vector<string> vs2 = recoverAllLCS(a, b, dp, i, j-1);
    for(auto x: vs1){
       vs2.push_back(x);
    }
    return vs2;
}

} vector returnAllLCS(string a, string b){ VVI dp = lcs(a, b); int n1=a.length(), n2 = b.length();

vector<string> v = recoverAllLCS(a, b, dp, n1, n2);
unordered_set<string> ans(v.begin(), v.end());
// for(auto x: ans){
//  reverse(x.begin(), x.end());
//  cout<<x<<endl;
// }
vector<string> final(ans.begin(), ans.end());
return final;

} ~~~~~

This is the code for first method.

VVVI dp(n1+1, VVI (n2+1, VI (n3+1, 0)));
	int ans=0;
	for(int i=1;i <= n1;i++){
		for(int j=1;j <= n2;j++){
			for(int k=1;k <= n3;k++){

				if(a[i] == b[j] && b[j] == c[k]){
					dp[i][j][k] = 1 + dp[i-1][j-1][k-1];
				}
				

				vector<int> di = {0, 0, -1};
				vector<int> dj = {0, -1, 0};
				vector<int> dk = {-1, 0, 0};

				for(int z=0;z<(int)di.size();z++){
					dp[i][j][k] = max(dp[i][j][k], dp[i+di[z]][j+dj[z]][k+dk[z]]);
				} 

				ans=max(ans, dp[i][j][k]);
			}
		}
	}

`