Print LCS Problem

#1

Why i am getting wrong output ?

#2

hello @vaishnavtannu
dont use for loop ,use while loop .
using for loop we will not be able to trace the path correctly because so many updation is happening at the same time in i and j.

#3

image

#4

#include
#include
using namespace std;

string lcs(string a ,string b)
{
int n = a.length();
int m = b.length();

int dp[n+1][m+1];
for(int i=0; i<=n; i++)
{
	dp[i][0]=0;

}
for(int i=0; i<=m ;i++)
{
	dp[0][i]=0;
}
for(int i=1; i<=n; i++)
{
	for(int j=1; j<=m; j++)
	{
		int q;
		if(a[i-1] == b[j-1])
		{
			q = 1+dp[i-1][j-1];

		}
		else
		{
			q = max(dp[i-1][j], dp[i][j-1]);
		}
		dp[i][j]=q;
	}
}



string ans="";
//ans[0] = '\0';
int i=n;
int j=m;
while(i > 0 && j>0)
{
	if(dp[i-1][j] == dp[i][j-1])
	{
		if(dp[i-1][j] != dp[i][j])
		{
			ans = a[i-1]+ans;
			i--;
			j--;
		}

	}
	else
	{
		if(dp[i-1][j] < dp[i][j-1])
		{
			j--;
		}
		else
		{
			i--;
		}
	}
}
return ans;

}

int main() {
string a, b;
cin>>a;
cin>>b;
string ans = lcs(a,b);
cout<<ans<<endl;
return 0;
}

Can someone pls tell why i am getting TLE

#5

hello sir isse saree test cases passs hogaye ?