Solution For Longest Common Subsequence

Problem:

Given two strings text1 and text2, return the length of their longest common subsequence.

A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

Example 1:

Input: text1 = “abcde”, text2 = “ace”
Output: 3
Explanation: The longest common subsequence is “ace” and its length is 3.

Example 2:

Input: text1 = “abc”, text2 = “def”
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Solution:

This problem can be solved using dynamic programming. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. We can solve this problem by using two strings. We can then compare the characters of the two strings and find the maximum length of a common subsequence.

We can use a dynamic programming matrix dp[i][j] to store the length of the longest common subsequence of the first i characters of text1 and the first j characters of text2.

dp[i][j] will be the length of the LCS of the two substrings ending at position i and j respectively.

dp[i][j] can be calculated as dp[i][j-1] if the current character of text2 is not in the LCS, or dp[i][j-1] + 1 if it is.

Similarly, dp[i][j] can be calculated as dp[i-1][j] if the current character of text1 is not in the LCS, or dp[i-1][j] + 1 if it is.

The final answer will be the value of dp[n][m], where n is the length of text1 and m is the length of text2.

Code:

int longestCommonSubsequence(string text1, string text2) {
int n = text1.length(), m = text2.length();
int dp[n+1][m+1];
for(int i=0;i<=n;i++)
dp[i][0] = 0;
for(int j=0;j<=m;j++)
dp[0][j] = 0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(text1[i-1] == text2[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[n][m];
}

The time complexity of the solution is O(nm), where n and m are the lengths of the input strings. The space complexity of the solution is O(nm).

Step by Step Implementation For Longest Common Subsequence

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int len1 = text1.length(), len2 = text2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
 
        for(int i = 0; i <= len1; i++) {
            for(int j = 0; j <= len2; j++) {
                if(i == 0 || j == 0)
                    dp[i][j] = 0;
                else if(text1.charAt(i-1) == text2.charAt(j-1))
                    dp[i][j] = 1 + dp[i-1][j-1];
                else
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
 
        return dp[len1][len2];
    }
}

def longestCommonSubsequence(text1, text2): 

# Initialize a 2D array with all 0s. The array will have text1.length + 1 rows and text2.length + 1 columns 

arr = [[0 for j in range(text2.length + 1)] for i in range(text1.length + 1)] 

# Iterate through each character in text1 and text2, and update the value in the 2D array if the characters match 

for i in range(1, text1.length + 1): 

for j in range(1, text2.length + 1): 

if text1[i - 1] == text2[j - 1]: 

arr[i][j] = arr[i - 1][j - 1] + 1 

else: 

arr[i][j] = max(arr[i][j - 1], arr[i - 1][j]) 

# The value in arr[text1.length][text2.length] will hold the length of the longest common subsequence 

return arr[text1.length][text2.length]

var longestCommonSubsequence = function(text1, text2) {
    // create a 2D array to hold the LCS values
    // text1 and text2 will be the same length
    let dp = new Array(text1.length + 1);
    
    // initialize the dp array
    for (let i = 0; i <= text1.length; i++) {
        dp[i] = new Array(text2.length + 1).fill(0);
    }
    
    // iterate through the dp array
    // start at 1 because we need to account for the empty strings
    for (let i = 1; i <= text1.length; i++) {
        for (let j = 1; j <= text2.length; j++) {
            // if the characters match, we take the diagonal value and add 1
            if (text1[i-1] === text2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                // if the characters don't match, we take the max of the left and top values
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    
    // the longest common subsequence will be the bottom right value in the dp array
    return dp[text1.length][text2.length];
};

One possible solution to the longest common subsequence problem in C++ is as follows:

int longestCommonSubsequence(string text1, string text2) 
{
    int n = text1.length();
    int m = text2.length();
 
    int L[n+1][m+1];
 
    for (int i=0; i<=n; i++) 
    {
        for (int j=0; j<=m; j++) 
        {
            if (i == 0 || j == 0)
                L[i][j] = 0;
 
            else if (text1[i-1] == text2[j-1])
                L[i][j] = L[i-1][j-1] + 1;
 
            else
                L[i][j] = max(L[i-1][j], L[i][j-1]);
        }
    }
 
    return L[n][m];
}

public int LongestCommonSubsequence(string text1, string text2) 
{ 
    int m = text1.Length, n = text2.Length; 
    int[,] L = new int[m + 1, n + 1]; 
  
    for (int i = 0; i <= m; i++) 
    { 
        for (int j = 0; j <= n; j++) 
        { 
            if (i == 0 || j == 0) 
                L[i, j] = 0; 
            else if (text1[i - 1] == text2[j - 1]) 
                L[i, j] = L[i - 1, j - 1] + 1; 
            else
                L[i, j] = Math.Max(L[i - 1, j], L[i, j - 1]); 
        } 
    } 
    return L[m, n]; 
}