K-ordered LCS problem

#1

can u please explain how to solve the probelm

#2

@Faizan-Ali-1395131367301898
As mentioned in the problem statement, given problem is quite similar to 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,mk),dp(n,m-1,k),dp(n-1,m-1,k-1)+1) when arr[n] not equal to arr[m]

Dp(n,m,k)=max(dp(n-1,mk),dp(n,m-1,k),dp(n-1,m-1,k)+1) when arr[n] not equal to arr[m]
Apply 3d dp ,hope you get it.

#3

I am not clear with problem statement can u please explain

#4

@Faizan-Ali-1395131367301898 basically hme longest common subsequence btana hai agr hm atmost k changes bhi krde first string me , A k-ordered LCS is defined to be the LCS of two sequences if you are allowed to change at most k elements in the first sequence to any value you wish to. Hope you get it.

#5

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.