How to approach this problem?

#1

Can anyone pls help me to approach this problem…

#2

hello @soumakpoddar55
given problem is quite similar to the standard LCS problem. We can have following dp state DP(n,m,k) = denotes LCS for first n number of first array, first m numbers of second array when we are allowed to change at max k numbers in first array.

Recursion look like this ->
DP(n,m,k) = max(DP(n-1,m,k), DP(n, m-1, k), DP(n-1, m-1, k-1)+1), if arr[n]!=arr[m]
DP(n,m,k) = max(DP(n-1,m,k), DP(n, m-1, k), DP(n-1, m-1, k)+1), if arr[n]==arr[m]

Time complexity = O(n * m * k)

#3

hey aman I have also seen the given article on hackerearth but I have not understood anything…can u pls explain the problem elaborately please…

#4

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.

1 Like
#5

why r u taking s1[i]=2*s2[i] and not s1[i]==s2[i]

#6

that is a typo … …

#7

yeah it should be j…