Length-of-longest-subsequence which is substring of other

#1

https://practice.geeksforgeeks.org/problems/find-length-of-longest-subsequence/0

plz provide the top down dp approach code for this question along with proper explaination …as i am unable to solve it…

Dont forward link of editorial…

#2

reply at the earliest…

#3

hello @S19LPPP0202
have u tried to code it .
if yes then pls share ur code link , i will debug it and give it to u.

otherwise wait i have to code it from scratch,because i havent tried this problem before

#4

Ok you plz code it from scratch in top down dp manner because I know lcs(string and subsequence) only and I am not able to correlate…plz code in top down dp

#5

pls chekc this ->

let me know if anything is not clear to u ,in the code

#6

plz explain the logic used in the code…

#7

logic is simple
i m finding dp[n][i] ->
which will tell me length of longest substring ending at index i-1 , which is also a subsequence of other string.

now solve(i,j)

if(dp[i][j]!=-1) that means we have already visited this state so simply return value .

otherwise if sn[i]==sm[j] then return 1+ solve(i-1,j-1) // i , j match so call for subproblem and add 1 to result

if sn[i]!=sm[j]
call for subproblem solve(i-1,j)

store ur computed answer in dp[i][j]=ans;
and then return dp[i][j].

now calculate max (dp[n][1],dp[n][2],dp[n][3]…dp[n][m])
and print it

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.