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 sequences 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++
< div id= "highlighter_959432" class = "syntaxhighlighter nogutter " ><table border= "0" cellpadding= "0" cellspacing= "0" ><tbody><tr><td class = "code" >< div class = "container" >< div class = "line number1 index0 alt2" ><code class = "comments" > // CPP program to find LCS of two arrays with </code></div><div class="line number2 index1 alt1"><code class="comments">// k changes allowed in first array. </code></div><div class="line number3 index2 alt2"><code class="preprocessor">#include <bits/stdc++.h> </code></div><div class="line number4 index3 alt1"><code class="keyword bold">using</code> <code class="keyword bold">namespace</code> <code class="plain">std; </code></div><div class="line number5 index4 alt2"><code class="preprocessor">#define MAX 10 </code></div><div class="line number6 index5 alt1"><code class="undefined spaces"> </code> </div><div class="line number7 index6 alt2"><code class="comments">// Return LCS with at most k changes allowed. </code></div><div class="line number8 index7 alt1"><code class="color1 bold">int</code> <code class="plain">lcs(</code><code class="color1 bold">int</code> <code class="plain">dp[MAX][MAX][MAX], </code><code class="color1 bold">int</code> <code class="plain">arr1[], </code><code class="color1 bold">int</code> <code class="plain">n, </code></div><div class="line number9 index8 alt2"><code class="undefined spaces"> </code><code class="color1 bold">int</code> <code class="plain">arr2[], </code><code class="color1 bold">int</code> <code class="plain">m, </code><code class="color1 bold">int</code> <code class="plain">k) </code></div><div class="line number10 index9 alt1"><code class="plain">{ </code></div><div class="line number11 index10 alt2"><code class="undefined spaces"> </code><code class="comments">// If at most changes is less than 0. </code></div><div class="line number12 index11 alt1"><code class="undefined spaces"> </code><code class="keyword bold">if</code> <code class="plain">(k < 0) </code></div><div class="line number13 index12 alt2"><code class="undefined spaces"> </code><code class="keyword bold">return</code> <code class="plain">-1e7; </code></div><div class="line number14 index13 alt1"><code class="undefined spaces"> </code> </div><div class="line number15 index14 alt2"><code class="undefined spaces"> </code><code class="comments">// If any of two array is over. </code></div><div class="line number16 index15 alt1"><code class="undefined spaces"> </code><code class="keyword bold">if</code> <code class="plain">(n < 0 || m < 0) </code></div><div class="line number17 index16 alt2"><code class="undefined spaces"> </code><code class="keyword bold">return</code> <code class="plain">0; </code></div><div class="line number18 index17 alt1"><code class="undefined spaces"> </code> </div><div class="line number19 index18 alt2"><code class="undefined spaces"> </code><code class="comments">// Making a reference variable to dp[n][m][k] </code></div><div class="line number20 index19 alt1"><code class="undefined spaces"> </code><code class="color1 bold">int</code><code class="plain">& ans = dp[n][m][k]; </code></div><div class="line number21 index20 alt2"><code class="undefined spaces"> </code> </div><div class="line number22 index21 alt1"><code class="undefined spaces"> </code><code class="comments">// If value is already calculated, return </code></div><div class="line number23 index22 alt2"><code class="undefined spaces"> </code><code class="comments">// that value. </code></div><div class="line number24 index23 alt1"><code class="undefined spaces"> </code><code class="keyword bold">if</code> <code class="plain">(ans != -1) </code></div><div class="line number25 index24 alt2"><code class="undefined spaces"> </code><code class="keyword bold">return</code> <code class="plain">ans; </code></div><div class="line number26 index25 alt1"><code class="undefined spaces"> </code> </div><div class="line number27 index26 alt2"><code class="undefined spaces"> </code><code class="comments">// calculating LCS with no changes made. </code></div><div class="line number28 index27 alt1"><code class="undefined spaces"> </code><code class="plain">ans = max(lcs(dp, arr1, n - 1, arr2, m, k), </code></div><div class="line number29 index28 alt2"><code class="undefined spaces"> </code><code class="plain">lcs(dp, arr1, n, arr2, m - 1, k)); </code></div><div class="line number30 index29 alt1"><code class="undefined spaces"> </code> </div><div class="line number31 index30 alt2"><code class="undefined spaces"> </code><code class="comments">// calculating LCS when array element are same. </code></div><div class="line number32 index31 alt1"><code class="undefined spaces"> </code><code class="keyword bold">if</code> <code class="plain">(arr1[n-1] == arr2[m-1]) </code></div><div class="line number33 index32 alt2"><code class="undefined spaces"> </code><code class="plain">ans = max(ans, 1 + lcs(dp, arr1, n - 1, </code></div><div class="line number34 index33 alt1"><code class="undefined spaces"> </code><code class="plain">arr2, m - 1, k)); </code></div><div class="line number35 index34 alt2"><code class="undefined spaces"> </code> </div><div class="line number36 index35 alt1"><code class="undefined spaces"> </code><code class="comments">// calculating LCS with changes made. </code></div><div class="line number37 index36 alt2"><code class="undefined spaces"> </code><code class="plain">ans = max(ans, 1 + lcs(dp, arr1, n - 1, </code></div><div class="line number38 index37 alt1"><code class="undefined spaces"> </code><code class="plain">arr2, m - 1, k - 1)); </code></div><div class="line number39 index38 alt2"><code class="undefined spaces"> </code> </div><div class="line number40 index39 alt1"><code class="undefined spaces"> </code><code class="keyword bold">return</code> <code class="plain">ans; </code></div><div class="line number41 index40 alt2"><code class="plain">} </code></div><div class="line number42 index41 alt1"><code class="undefined spaces"> </code> </div><div class="line number43 index42 alt2"><code class="comments">// Driven Program </code></div><div class="line number44 index43 alt1"><code class="color1 bold">int</code> <code class="plain">main() </code></div><div class="line number45 index44 alt2"><code class="plain">{ </code></div><div class="line number46 index45 alt1"><code class="undefined spaces"> </code><code class="color1 bold">int</code> <code class="plain">k = 1; </code></div><div class="line number47 index46 alt2"><code class="undefined spaces"> </code><code class="color1 bold">int</code> <code class="plain">arr1[] = { 1, 2, 3, 4, 5 }; </code></div><div class="line number48 index47 alt1"><code class="undefined spaces"> </code><code class="color1 bold">int</code> <code class="plain">arr2[] = { 5, 3, 1, 4, 2 }; </code></div><div class="line number49 index48 alt2"><code class="undefined spaces"> </code><code class="color1 bold">int</code> <code class="plain">n = </code><code class="keyword bold">sizeof</code><code class="plain">(arr1) / </code><code class="keyword bold">sizeof</code><code class="plain">(arr1[0]); </code></div><div class="line number50 index49 alt1"><code class="undefined spaces"> </code><code class="color1 bold">int</code> <code class="plain">m = </code><code class="keyword bold">sizeof</code><code class="plain">(arr2) / </code><code class="keyword bold">sizeof</code><code class="plain">(arr2[0]); </code></div><div class="line number51 index50 alt2"><code class="undefined spaces"> </code> </div><div class="line number52 index51 alt1"><code class="undefined spaces"> </code><code class="color1 bold">int</code> <code class="plain">dp[MAX][MAX][MAX]; </code></div><div class="line number53 index52 alt2"><code class="undefined spaces"> </code><code class="functions bold">memset</code><code class="plain">(dp, -1, </code><code class="keyword bold">sizeof</code><code class="plain">(dp)); </code></div><div class="line number54 index53 alt1"><code class="undefined spaces"> </code> </div><div class="line number55 index54 alt2"><code class="undefined spaces"> </code><code class="plain">cout << lcs(dp, arr1, n, arr2, m, k) << endl; </code></div><div class="line number56 index55 alt1"><code class="undefined spaces"> </code> </div><div class="line number57 index56 alt2"><code class="undefined spaces"> </code><code class="keyword bold">return</code> <code class="plain">0; </code></div><div class="line number58 index57 alt1"><code class="plain">} </code></div></div></td></tr></tbody></table></div> |
Java
// Java program to find LCS of two arrays with // k changes allowed in first array. import java.util.*; import java.io.*; class GFG { static int MAX = 10 ; // Return LCS with at most k changes allowed. static int lcs( int [][][] dp, int [] arr1, int n, int [] arr2, int m, int k) { // If at most changes is less than 0. if (k < 0 ) return - 10000000 ; // 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; try { // calculating LCS with no changes made. ans = Math.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 = Math.max(ans, 1 + lcs(dp, arr1, n - 1 , arr2, m - 1 , k)); // calculating LCS with changes made. ans = Math.max(ans, 1 + lcs(dp, arr1, n - 1 , arr2, m - 1 , k - 1 )); } catch (Exception e) { } // Storing the value in dp. dp[n][m][k] = ans; return ans; } // Driver Code public static void main(String[] args) { int k = 1 ; int [] arr1 = { 1 , 2 , 3 , 4 , 5 }; int [] arr2 = { 5 , 3 , 1 , 4 , 2 }; int n = arr1.length; int m = arr2.length; int [][][] dp = new int [MAX][MAX][MAX]; for ( int i = 0 ; i < MAX; i++) for ( int j = 0 ; j < MAX; j++) for ( int l = 0 ; l < MAX; l++) dp[i][j][l] = - 1 ; System.out.println(lcs(dp, arr1, n, arr2, m, k)); } } // This code is contributed by // krishnat208026 |
Python3
C#
// C# program to find LCS of two arrays with // k changes allowed in first array. using System; class GFG { static int MAX = 10; // Return LCS with at most // k changes allowed. static int lcs( int [,,] dp, int [] arr1, int n, int [] arr2, int m, int k) { // If at most changes is less than 0. if (k < 0) return -10000000; // 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; try { // calculating LCS with no changes made. ans = Math.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 = Math.Max(ans, 1 + lcs(dp, arr1, n - 1, arr2, m - 1, k)); // calculating LCS with changes made. ans = Math.Max(ans, 1 + lcs(dp, arr1, n - 1, arr2, m - 1, k - 1)); } catch (Exception e) { } return ans; } // Driver Code public static void Main(String[] args) { int k = 1; int [] arr1 = { 1, 2, 3, 4, 5 }; int [] arr2 = { 5, 3, 1, 4, 2 }; int n = arr1.Length; int m = arr2.Length; int [,,] dp = new int [MAX, MAX, MAX]; for ( int i = 0; i < MAX; i++) for ( int j = 0; j < MAX; j++) for ( int l = 0; l < MAX; l++) dp[i, j, l] = -1; Console.WriteLine(lcs(dp, arr1, n, arr2, m, k)); } } // This code is contributed by PrinciRaj1992 |
Javascript
<div id= "highlighter_52108" class= "syntaxhighlighter nogutter " ><table border= "0" cellpadding= "0" cellspacing= "0" ><tbody><tr><td class= "code" ><div class= "container" ><div class= "line number1 index0 alt2" ><code class= "plain" ><script> </code></div><div class= "line number2 index1 alt1" ><code class= "undefined spaces" > </code> </div><div class= "line number3 index2 alt2" ><code class= "comments" > // Javascript program to find LCS of two </code></div><div class="line number4 index3 alt1"><code class="comments">// arrays with k changes allowed in </code></div><div class="line number5 index4 alt2"><code class="comments">// first array. </code></div><div class="line number6 index5 alt1"><code class="plain">let MAX = 10; </code></div><div class="line number7 index6 alt2"><code class="undefined spaces"> </code> </div><div class="line number8 index7 alt1"><code class="comments">// Return LCS with at most k changes allowed. </code></div><div class="line number9 index8 alt2"><code class="keyword">function</code> <code class="plain">lcs(dp, arr1, n, arr2, m, k) </code></div><div class="line number10 index9 alt1"><code class="plain">{ </code></div><div class="line number11 index10 alt2"><code class="undefined spaces"> </code> </div><div class="line number12 index11 alt1"><code class="undefined spaces"> </code><code class="comments">// If at most changes is less than 0. </code></div><div class="line number13 index12 alt2"><code class="undefined spaces"> </code><code class="keyword">if</code> <code class="plain">(k < 0) </code></div><div class="line number14 index13 alt1"><code class="undefined spaces"> </code><code class="keyword">return</code> <code class="plain">-10000000; </code></div><div class="line number15 index14 alt2"><code class="undefined spaces"> </code> </div><div class="line number16 index15 alt1"><code class="undefined spaces"> </code><code class="comments">// If any of two array is over. </code></div><div class="line number17 index16 alt2"><code class="undefined spaces"> </code><code class="keyword">if</code> <code class="plain">(n < 0 || m < 0) </code></div><div class="line number18 index17 alt1"><code class="undefined spaces"> </code><code class="keyword">return</code> <code class="plain">0; </code></div><div class="line number19 index18 alt2"><code class="undefined spaces"> </code> </div><div class="line number20 index19 alt1"><code class="undefined spaces"> </code><code class="comments">// Making a reference variable </code></div><div class="line number21 index20 alt2"><code class="undefined spaces"> </code><code class="comments">// to dp[n][m][k] </code></div><div class="line number22 index21 alt1"><code class="undefined spaces"> </code><code class="plain">let ans = dp; </code></div><div class="line number23 index22 alt2"><code class="undefined spaces"> </code> </div><div class="line number24 index23 alt1"><code class="undefined spaces"> </code><code class="comments">// If value is already calculated, </code></div><div class="line number25 index24 alt2"><code class="undefined spaces"> </code><code class="comments">// return that value. </code></div><div class="line number26 index25 alt1"><code class="undefined spaces"> </code><code class="keyword">if</code> <code class="plain">(ans != -1) </code></div><div class="line number27 index26 alt2"><code class="undefined spaces"> </code><code class="keyword">return</code> <code class="plain">ans; </code></div><div class="line number28 index27 alt1"><code class="undefined spaces"> </code> </div><div class="line number29 index28 alt2"><code class="undefined spaces"> </code><code class="keyword">try</code> </div><div class="line number30 index29 alt1"><code class="undefined spaces"> </code><code class="plain">{ </code></div><div class="line number31 index30 alt2"><code class="undefined spaces"> </code> </div><div class="line number32 index31 alt1"><code class="undefined spaces"> </code><code class="comments">// Calculating LCS with no changes made. </code></div><div class="line number33 index32 alt2"><code class="undefined spaces"> </code><code class="plain">ans = Math.max(lcs(dp, arr1, n - 1, arr2, m, k), </code></div><div class="line number34 index33 alt1"><code class="undefined spaces"> </code><code class="plain">lcs(dp, arr1, n, arr2, m - 1, k)); </code></div><div class="line number35 index34 alt2"><code class="undefined spaces"> </code> </div><div class="line number36 index35 alt1"><code class="undefined spaces"> </code><code class="comments">// Calculating LCS when array element are same. </code></div><div class="line number37 index36 alt2"><code class="undefined spaces"> </code><code class="keyword">if</code> <code class="plain">(arr1[n - 1] == arr2[m - 1]) </code></div><div class="line number38 index37 alt1"><code class="undefined spaces"> </code><code class="plain">ans = Math.max(ans, 1 + lcs(dp, arr1, n - 1, </code></div><div class="line number39 index38 alt2"><code class="undefined spaces"> </code><code class="plain">arr2, m - 1, k)); </code></div><div class="line number40 index39 alt1"><code class="undefined spaces"> </code> </div><div class="line number41 index40 alt2"><code class="undefined spaces"> </code><code class="comments">// Calculating LCS with changes made. </code></div><div class="line number42 index41 alt1"><code class="undefined spaces"> </code><code class="plain">ans = Math.max(ans, 1 + lcs(dp, arr1, n - 1, </code></div><div class="line number43 index42 alt2"><code class="undefined spaces"> </code><code class="plain">arr2, m - 1, k - 1)); </code></div><div class="line number44 index43 alt1"><code class="undefined spaces"> </code><code class="plain">} </code><code class="keyword">catch</code> <code class="plain">(e) { } </code></div><div class="line number45 index44 alt2"><code class="undefined spaces"> </code><code class="keyword">return</code> <code class="plain">ans; </code></div><div class="line number46 index45 alt1"><code class="plain">} </code></div><div class="line number47 index46 alt2"><code class="undefined spaces"> </code> </div><div class="line number48 index47 alt1"><code class="comments">// Driver Code </code></div><div class="line number49 index48 alt2"><code class="plain">let k = 0; </code></div><div class="line number50 index49 alt1"><code class="plain">let arr1 = [ 1, 2, 3, 4, 5 ]; </code></div><div class="line number51 index50 alt2"><code class="plain">let arr2 = [ 5, 3, 1, 4, 2 ]; </code></div><div class="line number52 index51 alt1"><code class="plain">let n = arr1.length; </code></div><div class="line number53 index52 alt2"><code class="plain">let m = arr2.length; </code></div><div class="line number54 index53 alt1"><code class="undefined spaces"> </code> </div><div class="line number55 index54 alt2"><code class="plain">let dp = </code><code class="keyword">new</code> <code class="plain">Array(MAX); </code></div><div class="line number56 index55 alt1"><code class="keyword">for</code><code class="plain">(let i = 0; i < MAX; i++) </code></div><div class="line number57 index56 alt2"><code class="undefined spaces"> </code><code class="keyword">for</code><code class="plain">(let j = 0; j < MAX; j++) </code></div><div class="line number58 index57 alt1"><code class="undefined spaces"> </code><code class="keyword">for</code><code class="plain">(let l = 0; l < MAX; l++) </code></div><div class="line number59 index58 alt2"><code class="undefined spaces"> </code><code class="plain">dp = -1; </code></div><div class="line number60 index59 alt1"><code class="undefined spaces"> </code> </div><div class="line number61 index60 alt2"><code class="plain">document.write(lcs(dp, arr1, n, arr2, m, k)); </code></div><div class="line number62 index61 alt1"><code class="undefined spaces"> </code> </div><div class="line number63 index62 alt2"><code class="comments">// This code is contributed by shivanisinghss2110 </code></div><div class="line number64 index63 alt1"><code class="undefined spaces"> </code> </div><div class="line number65 index64 alt2"><code class="plain"></script></code></div></div></td></tr></tbody></table></div> |
Output
4
Time Complexity: O(N*M*K).
Auxiliary Space: O(MAX3)