How to approach such questions?

#1

how to approach such questions? LCS 3d article is on gfg but unable to solve this one

#2

hello @sunneykumar309

see logic is simple .( 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.

for optimisation use 3d dp table

#3

how to improve in dp section

#4

i am unable to think recursively

#5

i have already explained the recursive approach if u have solved lcs then this is just a simple variation of that problem.

just u need to use one 3 array to memoise result.

dp[i][j][k]

#6

bro, how to improve in dp?

#7

u just have to use one addtional 3d array to store ur computed result to avoid its recomputation.
refer this->

#8

in 19 line it is always true that
why you are adding +1
it means that if someone decreased a value of k then ans = +1

#9

we have made a[i]==b[j] thats why +1

#10

i am getting MLE error

#11

use int in place of long long

1 Like
#12

thankx for your time

#13

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.