plz help me in approaching this problem, plz
K - ordered LCS
hello @Bhavya_Goel
please watch lcs video of dynamic programming first.
i am assuming that u have solved lcs problem
suppose we have s1and s2 as string and k.
i=0 (for string s1)
j=0(for string s2)
if s1[i]==s2[j]
then ans=1+solvefor(i+1,j+1,k)
if(s1[i]!=s2[j] (we have two options)
-
ans=solvefor(i+1,j,k) or solvefor(i,j+1,k) take maximum among them // we did similar thing in lcs
-
if k>0 then i can use 1 k to make them equal and lcs in that case will be
ans=1+solvefor(i+1,j+1,k-1) // k-1 because i have used 1 k to make them equal
among those two options whichever will give maximum answe we will consider that.
we have to take 3d dp arr
yeah . . . . . . … . .