Tutorialspoint.dev

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 }.



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 <bits/stdc++.h>
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[0]);
    int m = sizeof(arr2) / sizeof(arr2[0]);
  
    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).

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter