Cant figure out approach

#1

Please tell me how to appraoch the above problem

#2

hello @jayasmit98

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.