# Longest Common Subsequence with at most k changes allowed

Given two sequence P and Q of numbers. The task is to find Longest Common Subsequence of two sequence if we are allowed to change at most k element in first sequence to any value.

Examples:

```Input : P = { 8, 3 }
Q = { 1, 3 }
K = 1
Output : 2
If we change first element of first
sequence from 8 to 1, both sequences
become same.

Input : P = { 1, 2, 3, 4, 5 }
Q = { 5, 3, 1, 4, 2 }
K = 1
Output : 3
By changing first element of first
sequence to 5 to get the LCS ( 5, 3, 4 }.
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

The idea is to use Dynamic Programming. Define a 3D matrix dp[][][], where dp[i][j][k] defines the Longest Common Subsequence for the first i numbers of first array, first j number of second array when we are allowed to change at max k number in the first array.
Therefore, recursion will look like

```If P[i] != Q[j],
dp[i][j][k] = max(dp[i - 1][j][k],
dp[i][j - 1][k],
dp[i - 1][j - 1][k - 1] + 1)
If P[i] == Q[j],
dp[i][j][k] = max(dp[i - 1][j][k],
dp[i][j - 1][k],
dp[i - 1][j - 1][k] + 1)
```

Below is The implementation of this approach:

## C++

 `// CPP program to find LCS of two arrays with ` `// k changes allowed in first array. ` `#include ` `using` `namespace` `std; ` `#define MAX 10 ` ` `  `// Return LCS with at most k changes allowed. ` `int` `lcs(``int` `dp[MAX][MAX][MAX], ``int` `arr1[], ``int` `n, ` `                       ``int` `arr2[], ``int` `m, ``int` `k) ` `{ ` `    ``// If at most changes is less than 0. ` `    ``if` `(k < 0) ` `        ``return` `-1e7; ` ` `  `    ``// If any of two array is over. ` `    ``if` `(n < 0 || m < 0) ` `        ``return` `0; ` ` `  `    ``// Making a reference variable to dp[n][m][k] ` `    ``int``& ans = dp[n][m][k]; ` ` `  `    ``// If value is already calculated, return ` `    ``// that value. ` `    ``if` `(ans != -1) ` `        ``return` `ans; ` ` `  `    ``// calculating LCS with no changes made. ` `    ``ans = max(lcs(dp, arr1, n - 1, arr2, m, k),  ` `              ``lcs(dp, arr1, n, arr2, m - 1, k)); ` ` `  `    ``// calculating LCS when array element are same. ` `    ``if` `(arr1[n] == arr2[m]) ` `        ``ans = max(ans, 1 + lcs(dp, arr1, n - 1,  ` `                                ``arr2, m - 1, k)); ` ` `  `    ``// calculating LCS with changes made. ` `    ``ans = max(ans, 1 + lcs(dp, arr1, n - 1,  ` `                          ``arr2, m - 1, k - 1)); ` ` `  `    ``return` `ans; ` `} ` ` `  `// Driven Program ` `int` `main() ` `{ ` `    ``int` `k = 1; ` `    ``int` `arr1[] = { 1, 2, 3, 4, 5 }; ` `    ``int` `arr2[] = { 5, 3, 1, 4, 2 }; ` `    ``int` `n = ``sizeof``(arr1) / ``sizeof``(arr1); ` `    ``int` `m = ``sizeof``(arr2) / ``sizeof``(arr2); ` ` `  `    ``int` `dp[MAX][MAX][MAX]; ` `    ``memset``(dp, -1, ``sizeof``(dp)); ` ` `  `    ``cout << lcs(dp, arr1, n, arr2, m, k) << endl; ` ` `  `    ``return` `0; ` `} `

## Python3

 `# Python3 program to find LCS of two arrays  ` `# with k changes allowed in the first array.  ` `MAX` `=` `10`  ` `  `# Return LCS with at most k changes allowed.  ` `def` `lcs(dp, arr1, n, arr2, m, k):  ` `  `  `    ``# If at most changes is less than 0.  ` `    ``if` `k < ``0``: ` `        ``return` `-``(``10` `*``*` `7``)  ` ` `  `    ``# If any of two array is over.  ` `    ``if` `n < ``0` `or` `m < ``0``:  ` `        ``return` `0`  ` `  `    ``# Making a reference variable to dp[n][m][k]  ` `    ``ans ``=` `dp[n][m][k]  ` ` `  `    ``# If value is already calculated,  ` `    ``# return that value.  ` `    ``if` `ans !``=` `-``1``:  ` `        ``return` `ans  ` ` `  `    ``# calculating LCS with no changes made.  ` `    ``ans ``=` `max``(lcs(dp, arr1, n ``-` `1``, arr2, m, k),  ` `            ``lcs(dp, arr1, n, arr2, m ``-` `1``, k))  ` ` `  `    ``# calculating LCS when array element are same.  ` `    ``if` `arr1[n``-``1``] ``=``=` `arr2[m``-``1``]:  ` `        ``ans ``=` `max``(ans, ``1` `+` `lcs(dp, arr1, n ``-` `1``,  ` `                                ``arr2, m ``-` `1``, k))  ` ` `  `    ``# calculating LCS with changes made.  ` `    ``ans ``=` `max``(ans, lcs(dp, arr1, n ``-` `1``,  ` `                        ``arr2, m ``-` `1``, k ``-` `1``))  ` ` `  `    ``return` `ans  ` `  `  `# Driven Program  ` `if` `__name__ ``=``=` `"__main__"``: ` `  `  `    ``k ``=` `1`  `    ``arr1 ``=` `[``1``, ``2``, ``3``, ``4``, ``5``]  ` `    ``arr2 ``=` `[``5``, ``3``, ``1``, ``4``, ``2``]   ` `    ``n ``=` `len``(arr1)  ` `    ``m ``=` `len``(arr2)  ` ` `  `    ``dp ``=` `[[[``-``1` `for` `i ``in` `range``(``MAX``)] ``for` `j ``in` `range``(``MAX``)] ``for` `k ``in` `range``(``MAX``)] ` `     `  `    ``print``(lcs(dp, arr1, n, arr2, m, k))  ` ` `  `# This code is contributed by Rituraj Jain `

Output:

```3
```

Time Complexity: O(N*M*K).