Make Longest Common Subsequence at least K
Given two strings A of length N and B of length M. These strings contain lowercase English alphabets. You are also given an integer K. You can change the character of x of string A to any other character y. The cost of this conversion is abs(ASCII(x)- ASCII(y)). Find the minimum cost required such that the length of the Longest Common Subsequence (LCS) of A and B is at least K.
Constraints:
- 1 <= N <= 100
- 1 <= M <= 100
Examples:
Input: N = 5, M = 4, K = 3, A = “abcba”, B = “acyx”
Output: 22
Explanation: As the minimum length of the subsequences is 3, we have to match any 3 characters of A with B. We can convert A[3] to “x” with cost = 22, then we can get the Longest Common Subsequence as “acx” of length 3.Input: N = 3, M = 3, K = 3, A = “abc”, B = “abc”
Output: 0
Explanation: As the minimum length is 3 both the string is of length 3 and every character is matches no change is needed and the minimum cost will be 0.
Approach: To solve the problem follow the below idea
The problem can be solved using Dynamic Programming. We can make a recursive function rec(i1, i2, K) which returns the minimum cost to have a Longest Common Subsequence of length K if we are at index i1 in string A and index i2 in string B. For any function rec(i1, i2, K) we have 3 choices:
- Skip the i1th character of A, cost = rec(i1 – 1, i2, K)
- Skip the i2th character of B, cost = rec(i1, i2 – 1, K)
- Include the i1th character of A and i2th character of B for LCS with cost = abs(A[i1] – B[i2]) + rec(i1 – 1, i2 – 1, K – 1)
Use a 3D array dp[N][M][K] for memoization. Iterate for each N, M and K get the minimum cost.
Below are the steps to solve this problem:
- As maximum length can be 100, Initialize a 3D dp of size [105] [105] [105] filled with -1.
- If characters present at index M -1 and N -1 are equal, we need 0 cost.
- Otherwise, get the absolute difference of characters A[n] and B[m] and add it as cost.
- Look for the minimum cost from { rec(A, B, n – 1, m, k), x + rec(A, B, n – 1, m – 1, k – 1), rec(A, B, n, m – 1, k) }. And proceed further with it.
- Return the dp[n][m][k] as the minimum cost.
Below is the implementation of the code:
C++
// C++ Implementation #include <bits/stdc++.h> using namespace std; // Declare a dp int dp[105][105][105]; // Function to iterate in dp int rec(string A, string B, int i1, int i2, int k) { // If length of lcs string is reached if (k == 0) return 0; // if any of the string is completed if (i1 < 0 || i2 < 0) { if (k == 0) { return 0; } return 1e9; } // If value of that is already found if (dp[i1][i2][k] != -1) { return dp[i1][i2][k]; } // If values are equal if (A[i1] == B[i2]) { dp[i1][i2][k] = rec(A, B, i1 - 1, i2 - 1, k - 1); } // Otherwise check by adding cost else { int cost = abs (( int )A[i1] - ( int )B[i2]); dp[i1][i2][k] = min({ rec(A, B, i1 - 1, i2, k), cost + rec(A, B, i1 - 1, i2 - 1, k - 1), rec(A, B, i1, i2 - 1, k) }); } // Return the value return dp[i1][i2][k]; } // Function to find minimum cost to get lcs of length // k int generateSub(string A, string B, int N, int M, int K) { // Fill the dp with -1 memset (dp, -1, sizeof (dp)); // Iterate in dp return rec(A, B, N - 1, M - 1, K); } // Driver code int main() { int K = 3; string A = "abcba" ; string B = "acyx" ; int N = A.length(); int M = B.length(); // Function call cout << generateSub(A, B, N, M, K); return 0; } |
Java
import java.util.Arrays; public class LCS { // Declare a dp static int [][][] dp; // Function to iterate in dp static int rec(String A, String B, int i1, int i2, int k) { // If length of LCS string is reached if (k == 0 ) return 0 ; // if any of the string is completed if (i1 < 0 || i2 < 0 ) { if (k == 0 ) { return 0 ; } return ( int ) 1e9; } // If value of that is already found if (dp[i1][i2][k] != - 1 ) { return dp[i1][i2][k]; } // If values are equal if (A.charAt(i1) == B.charAt(i2)) { dp[i1][i2][k] = rec(A, B, i1 - 1 , i2 - 1 , k - 1 ); } // Otherwise check by adding cost else { int cost = Math.abs(( int ) A.charAt(i1) - ( int ) B.charAt(i2)); dp[i1][i2][k] = Math.min( Math.min(rec(A, B, i1 - 1 , i2, k), cost + rec(A, B, i1 - 1 , i2 - 1 , k - 1 )), rec(A, B, i1, i2 - 1 , k)); } // Return the value return dp[i1][i2][k]; } // Function to find minimum cost to get LCS of length k static int generateSub(String A, String B, int N, int M, int K) { // Fill the dp with -1 dp = new int [N][M][K + 1 ]; for ( int i = 0 ; i < N; i++) { for ( int j = 0 ; j < M; j++) { Arrays.fill(dp[i][j], - 1 ); } } // Iterate in dp return rec(A, B, N - 1 , M - 1 , K); } // Driver code public static void main(String[] args) { int K = 3 ; String A = "abcba" ; String B = "acyx" ; int N = A.length(); int M = B.length(); // Function call System.out.println(generateSub(A, B, N, M, K)); } } // This code is contributed by akshitaguprzj3 |
Python3
def generate_sub(A, B, K): N, M = len (A), len (B) dp = [[[ - 1 for _ in range (K + 1 )] for _ in range (M + 1 )] for _ in range (N + 1 )] def rec(i1, i2, k): if k = = 0 : return 0 if i1 < 0 or i2 < 0 : if k = = 0 : return 0 return float ( 'inf' ) if dp[i1][i2][k] ! = - 1 : return dp[i1][i2][k] if A[i1] = = B[i2]: dp[i1][i2][k] = rec(i1 - 1 , i2 - 1 , k - 1 ) else : cost = abs ( ord (A[i1]) - ord (B[i2])) dp[i1][i2][k] = min (rec(i1 - 1 , i2, k), cost + rec(i1 - 1 , i2 - 1 , k - 1 ), rec(i1, i2 - 1 , k)) return dp[i1][i2][k] return rec(N - 1 , M - 1 , K) # Driver code K = 3 A = "abcba" B = "acyx" result = generate_sub(A, B, K) print (result) |
C#
using System; class Program { // Declare a dp static int [,,] dp = new int [105, 105, 105]; // Function to iterate in dp static int Rec( string A, string B, int i1, int i2, int k) { // If length of lcs string is reached if (k == 0) return 0; // if any of the string is completed if (i1 < 0 || i2 < 0) { if (k == 0) return 0; return int .MaxValue; } // If value of that is already found if (dp[i1, i2, k] != -1) return dp[i1, i2, k]; // If values are equal if (A[i1] == B[i2]) dp[i1, i2, k] = Rec(A, B, i1 - 1, i2 - 1, k - 1); else { // Otherwise check by adding cost int cost = Math.Abs(( int )A[i1] - ( int )B[i2]); dp[i1, i2, k] = Math.Min(Rec(A, B, i1 - 1, i2, k), Math.Min(cost + Rec(A, B, i1 - 1, i2 - 1, k - 1), Rec(A, B, i1, i2 - 1, k))); } // Return the value return dp[i1, i2, k]; } // Function to find minimum cost to get lcs of length // k static int GenerateSub( string A, string B, int N, int M, int K) { // Fill the dp with -1 for ( int i = 0; i < 105; i++) for ( int j = 0; j < 105; j++) for ( int l = 0; l < 105; l++) dp[i, j, l] = -1; // Iterate in dp return Rec(A, B, N - 1, M - 1, K); } // Driver code static void Main() { int K = 3; string A = "abcba" ; string B = "acyx" ; int N = A.Length; int M = B.Length; // Function call Console.WriteLine(GenerateSub(A, B, N, M, K)); } } |
Javascript
function generateSub(A, B, K) { const N = A.length; const M = B.length; // Initialize a 3D array for memoization const dp = Array.from({ length: N + 1 }, () => Array.from({ length: M + 1 }, () => Array(K + 1).fill(-1) ) ); // Recursive function to calculate the minimum cost function rec(i1, i2, k) { // If k becomes 0, no more substitutions are allowed if (k === 0) { return 0; } // Base cases if (i1 < 0 || i2 < 0) { return (k === 0) ? 0 : Infinity; } // Check if the result is already memoized if (dp[i1][i2][k] !== -1) { return dp[i1][i2][k]; } // If the characters at the current positions are equal if (A[i1] === B[i2]) { dp[i1][i2][k] = rec(i1 - 1, i2 - 1, k - 1); } else { // Calculate cost for substitution const cost = Math.abs(A[i1].charCodeAt(0) - B[i2].charCodeAt(0)); // Update the memoization table with the minimum cost dp[i1][i2][k] = Math.min( rec(i1 - 1, i2, k), cost + rec(i1 - 1, i2 - 1, k - 1), rec(i1, i2 - 1, k) ); } return dp[i1][i2][k]; } // Start the recursion from the last characters of both strings return rec(N - 1, M - 1, K); } // Driver code const K = 3; const A = "abcba" ; const B = "acyx" ; const result = generateSub(A, B, K); console.log(result); |
22
Time Complexity: O(N * M * K), where N is the length of string A and M is the length of string B.
Auxiliary Space: O(N * M * K)
Contact Us