Longest Common Subsequence
You have been given two Strings “STR1” and “STR2” of characters. Your task is to find the length of the longest common subsequence.

A String ‘a’ is a subsequence of a String ‘b’ if ‘a’ can be obtained from ‘b’ by deletion of several (possibly, zero or all) characters. A common subsequence of two Strings is a subsequence that is common to both Strings.

Input Format :

The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows. The first input line of each test case contains two space-separated Strings “STR1” and “STR2” representing two Strings.

Output Format :

For each test case, print the length of the longest common subsequence. Print the output of each test case in a separate line.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints :

1

Question

Longest Common Subsequence

You have been given two Strings “STR1” and “STR2” of characters. Your task is to find the length of the longest common subsequence.

A String ‘a’ is a subsequence of a String ‘b’ if ‘a’ can be obtained from ‘b’ by deletion of several (possibly, zero or all) characters. A common subsequence of two Strings is a subsequence that is common to both Strings.

Input Format :

The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows. 

The first input line of each test case contains two space-separated Strings “STR1” and “STR2” representing two Strings.

Output Format :

For each test case, print the length of the longest common subsequence. 

Print the output of each test case in a separate line.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 50 
1 <= |STR1| <= 10^2
1 <= |STR2| <= 10^2

Where |STR1| and |STR2| denote the length of “STR1” and “STR2” respectively. 

Time Limit: 1 sec

Accepted Answer

This problem can be solved using recursion. In this approach, we will start form last element of both the strings. If elements at the last matches then we will decrement length of both the string else we will decrement the length of either of the string.
lcs(s1, s2, n, m):
if n == 0 or m == 0:
return 0
if s1[n-1] == s2[m - 1]:
return 1 + lcs(s1, s2, n-1, m-1)
else:
return max(lcs(s1, s2, n-1, m), lcs(s1, s2, n, m-1))

But this approach would result in TLE for longer test cases. It can be optimized using dynamic programming.
In the top down approach, we make a table of size [m+1][n+1] where m and n are the length of the strings. The intermediate row and column of the table indicates what will be the value of the longest common subsequence if its called for the smaller inputs.
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])

Accepted Answer

Recursive Brute Force

The basic idea of this approach is to break the original problem into sub-problems. Let us assume we want to find the length of the longest common subsequence of “STR1” and “STR2” whose length is ‘N’ and ‘M’ respectively.

Now, let us define a recursive function

LCS(Int I, int J, string STR1, string STR2)

Which returns the length of the longest common subsequence of string STR1[0: I-1] and STR1[0: J-1] where STR1[l: R] denotes the substring of “STR1” having characters from index ‘l’ to index ‘R’.

Now, consider the following steps :

If ( I == 0 ) i.e. “STR1” is empty then, the length of the LCS will be 0. So return 0.
Similarly, if ( J == 0 ) return 0.
Now if ( STR1[I-1] == STR2[J-1] ) which means the last character of both string matches then it is optimal to include the current character into the LCS. Therefore, find the LCS of the remaining characters of both strings. So return LCS(I-1, J-1, STR1, STR2) + 1
Otherwise, we can not have both STR1[I-1] and STR2[J-1] at the end of the LCS which means either of them can be ignored. Now there are two possibilities, either we ignore STR1[I-1] and get the LCS of the rest of the characters and vice versa. We should choose the option which maximizes the LCS i.e. return max( LCS(I-1, J, STR1, STR2), LCS(I, J-1, STR1, STR2).

Space Complexity: O(1)Explanation:

O(max(N, M)), where ‘N’ and ‘M’ are the length of 'STR1' and ‘STR2’ respectively.

Since we are using a recursive function to find the length of LCS and in the worst case, there may be max(N, M) state in the call stack. So the overall space complexity will be O(max(N, M)).

Time Complexity: O(1)Explanation:

O(2^(N+M), where ‘N’ and ‘M’ are the length of 'STR1' and ‘STR2’ respectively.

Since we are using a recursive function to find the length of LCS where we are comparing each subsequence of the first string with the second string. So the overall time complexity will be O(2^(N + M)).

Accepted Answer

Recursive + Memoization.

Let us observe the recursion tree for the case where STR1 = “abc” and STR2 = “cabd”

After observing the tree, we’ll find that there are some redundant function calls which means that there are some overlapping subproblems. The repetition of such sub-problems suggests that we can use dynamic programming to optimize our approach.

The key idea behind a dynamic programming approach is to use memoization, i.e. we’ll save the result of our sub-problem in a matrix so that it can be used later on.

Let DP[ I ][ J ] be our dynamic programming matrix to store the length of LCS of substring STR1[0: i-1] and STR2[0: j-1].

Now, consider the following steps:

Before calling the function for any valid (I, J), we will first check whether we have already a solution corresponding to the (I, J), if we have already a solution then we return the solution else we will solve it with the following steps :
If ( I == 0 ) i.e. “STR1” is empty then, the length of the LCS will be 0. So the answer is 0.
Similarly, if ( J == 0 ) the answer is 0.
Now if ( STR1[I-1] == STR2[J-1] ) which means the last character of both string matches then it is optimal to include the current character in the LCS. Therefore, find the LCS of the remaining characters of both strings. So return LCS(I-1, J-1, STR1, STR2) + 1
Otherwise, we can not have both STR1[I-1] and STR2[J-1] at the end of the LCS which means either of them can be ignored. Now there are two possibilities, either we ignore STR1[I-1] and get the LCS of the rest of the characters and vice versa. We should choose the option which maximizes the LCS i.e. the answer will be max( LCS(I-1, J, STR1, STR2), LCS(I, J-1, STR1, STR2).
Store the answer in the “DP” table for later use.

Space Complexity: O(m*n) - For 2d arraysExplanation:

O(N * M), where ‘N’ and ‘M’ are the length of 'STR1' and ‘STR2’ respectively.

The only extra space which is being used is the dynamic programming table dp[][] of (N+1)*(M+1) dimension. Thus, the overall space complexity will be O(N*M).

Time Complexity: OtherExplanation:

O(N * M), where ‘N’ and ‘M’ are the length of 'STR1' and ‘STR2’ respectively.

There will be only N*M distinct recursion calls in recursion because we are saving the result so there will be no redundant calls. Thus, the overall time complexity will be O(N*M).

C++ (g++ 5.4)

/*

    Time Complexity: O(N * M)

    Space Complexity: O(N * M)



    where 'N' and 'M' are the lengths of the "str1" and "str2" respectively.

*/



// Returns the length of lcs of "str1" and "str2".

int lcs(int i, int j, string & str1, string & str2, vector < vector < int >> & dp) {

    if (i == 0 || j == 0) {

        // One of the string is empty.

        return 0;

    } else if (dp[i][j] != -1) {

        // Solution already exists.

        return dp[i][j];

    } else if (str1[i - 1] == str2[j - 1]) {

        /* 

          The last character of both String matches. Include the current character in LCS.

          int length = lcs(i - 1, j - 1, str1, str2, dp) + 1;

        */

        int length = lcs(i - 1, j - 1, str1, str2, dp) + 1;



        // Store the result in "dp" matrix.

        dp[i][j] = length;



        return length;

    } else {

        // Get the maximum of both possibilities.

        int length = max(lcs(i, j - 1, str1, str2, dp), lcs(i - 1, j, str1, str2, dp));



        // Store the result in "dp" matrix.

        dp[i][j] = length;



        return length;

    }

}



int getLengthOfLCS(string & str1, string & str2) {

    int n = str1.size();

    int m = str2.size();



    // Dynamic programming matrix to store the length of LCS.

    vector < vector < int >> dp(n + 1, vector < int > (m + 1, -1));



    // Get the length of LCS.

    return lcs(str1.size(), str2.size(), str1, str2, dp);

}

Python (3.5)

'''

    Time Complexity: O(N * M)

    Space Complexity: O(N * M)



    where 'N' and 'M' are the lengths of the "str1" and "str2" respectively.

'''



def lcs(i, j, str1, str2, dp):



    # One of the string is empty.

    if (i == 0) or (j == 0):

        return 0;

    

    if dp[i][j] != -1:

        return dp[i][j]



    '''

        The last character of both string matches.

        Include the current character in LCS.

    '''

    if str1[i - 1] == str2[j - 1]:

        dp[i][j] = lcs(i - 1, j - 1, str1, str2, dp) + 1

    

    # Get the maximum of both possibilities.

    else:

        dp[i][j] = max(lcs(i, j - 1, str1, str2, dp), lcs(i - 1, j, str1, str2, dp))

    

    return dp[i][j]

    



def getLengthOfLCS(str1, str2):    

    n = len(str1)

    m = len(str2)



    # Dynamic programming matrix to store the length of LCS.

    dp = [[-1] * (m + 1) for _ in range(n + 1)] 

    

    # Get the length of LCS.

    return lcs(n, m, str1, str2, dp);

Java (SE 1.8)

/*

    Time Complexity: O(N * M)

    Space Complexity: O(N * M)



    where 'N' and 'M' are the lengths of the "str1" and "str2" respectively.

*/



import java.util.ArrayList;



public class Solution {

    // Returns the length of lcs of "str1" and "str2".

    private static int lcs(int i, int j, String str1, String str2, ArrayList < ArrayList < Integer >> dp) {

        if (i == 0 || j == 0) {

            // One of the String is empty.

            return 0;

        } else if (dp.get(i).get(j) != -1) {

            // Solution already exists.

            return dp.get(i).get(j);

        } else if (str1.charAt(i - 1) == str2.charAt(j - 1)) {



            /* 

              The last character of both String matches. 

              Include the current character in LCS.

              int length = lcs(i - 1, j - 1, str1, str2, dp) + 1;

            */

            int length = lcs(i - 1, j - 1, str1, str2, dp) + 1;



            // Store the result in "dp" matrix.

            dp.get(i).set(j, length);



            return length;

        } else {

            // Get the maximum of both possibilities.

            int length = Math.max(lcs(i, j - 1, str1, str2, dp), lcs(i - 1, j, str1, str2, dp));



            // Store the result in "dp" matrix.

            dp.get(i).set(j, length);



            return length;

        }

    }



    public static int getLengthOfLCS(String str1, String str2) {

        int n = str1.length();

        int m = str2.length();



        // Dynamic programming matrix to store the length of LCS.

        ArrayList < ArrayList < Integer >> dp = new ArrayList < ArrayList < Integer >> (n + 1);



        for (int i = 0; i <= n; i++) {

            dp.add(new ArrayList < Integer > (m + 1));

            for (int j = 0; j <= m; j++) {

                dp.get(i).add(-1);

            }

        }



        // Get the length of LCS.

        return lcs(n, m, str1, str2, dp);

    }

}

Accepted Answer

Iterative Dynamic Programming + Memoization.

The basic idea of this approach is to solve the problem iteratively.

Let DP[I] J] be our dynamic programming matrix to store the length of LCS of substring STR1[0: I-1] and STR2[0:J-1].

Now, consider the following steps:

Start traversing the “STR1” using a variable ‘i’
Create a nested loop and start traversing the “STR2” using a variable ‘J’

If either ‘I’ or ‘J’ is zero then DP[I][J] = 0 because one of the strings is empty.
If ( STR1[I-1] == STR2[J-1] ) which means the current character of both strings matches then it is optimal to include the current character in the LCS. Therefore, find the LCS of the remaining characters of both strings. DP[I][J] = DP[I-1][J-1] + 1

Otherwise, we can not have both STR1[I-1] and STR2[J-1] at the end of the LCS which means either of them can be ignored. Now there are two possibilities, either we ignore STR1[I-1] and get the LCS of the rest of the characters and vice versa. We should choose the option which maximises the LCS i.e. DP[I][J] = max(DP[I-1][J], DP[I][J-1])

Now we can get the length of LCS from DP[N][M] where ‘N’ and ‘M’ are the length of “STR1” and “STR2” respectively.

Space Complexity: O(m*n) - For 2d arraysExplanation:

O(N * M), where ‘N’ and ‘M’ are the length of 'STR1' and ‘STR2’ respectively.

The only extra space which is being used is the dynamic programming table dp[][] of (N+1)*(M+1) dimension. Thus, the overall space complexity will be O(N*M).

Time Complexity: O(m*n) - For 2d arraysExplanation:

O(N * M), where ‘N’ and ‘M’ are the length of 'STR1' and ‘STR2’ respectively.

Since we are traversing through both strings using a nested loop. The overall time complexity will be O(N * M).

Java (SE 1.8)

/*

    Time Complexity: O(N * M)

    Space Complexity: O(N * M)



    where 'N' and 'M' are the lengths of the "str1" and "str2" respectively.

*/



import java.util.ArrayList;



public class Solution {

    public static int getLengthOfLCS(String str1, String str2) {

        int n = str1.length();

        int m = str2.length();



        // Dynamic programming matrix to store the length of getLengthOfLCS of subString.

        ArrayList < ArrayList < Integer >> dp = new ArrayList < ArrayList < Integer >> (n + 1);



        for (int i = 0; i <= n; i++) {

            dp.add(new ArrayList < Integer > (m + 1));



            for (int j = 0; j <= m; j++) {

                dp.get(i).add(-1);

            }

        }



        // Start traversing through the "str1".

        for (int i = 0; i <= n; i++) {

            for (int j = 0; j <= m; j++) {

                if (i == 0 || j == 0) {

                    // Length of one of the subtring is zero.

                    dp.get(i).set(j, 0);

                } else if (str1.charAt(i - 1) == str2.charAt(j - 1)) {

                    // The last character of both subString matches.

                    dp.get(i).set(j, dp.get(i - 1).get(j - 1) + 1);

                } else {

                    // Get the maximum of both possibilities.

                    dp.get(i).set(j, Math.max(dp.get(i).get(j - 1), dp.get(i - 1).get(j)));

                }

            }

        }



        return dp.get(n).get(m);

    }

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N * M)

    Space Complexity: O(N * M)



    where 'N' and 'M' are the lengths of the "str1" and "str2" respectively.

*/



int getLengthOfLCS(string & str1, string & str2) {

    int n = str1.size();

    int m = str2.size();



    // Dynamic programming matrix to store the length of getLengthOfLCS of substring.

    vector < vector < int >> dp(n + 1, vector < int > (m + 1, 0));



    // Start traversing through the "str1".

    for (int i = 0; i <= n; i++) {

        for (int j = 0; j <= m; j++) {

            if (i == 0 || j == 0) {

                // Length of one of the subtring is zero.

                dp[i][j] = 0;

            } else if (str1[i - 1] == str2[j - 1]) {

                // The last character of both substring matches.

                dp[i][j] = dp[i - 1][j - 1] + 1;

            } else {

                // Get the maximum of both possibilities.

                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);

            }

        }

    }



    return dp[n][m];

}

Python (3.5)

'''

    Time Complexity: O(N * M)

    Space Complexity: O(N * M)



    where 'N' and 'M' are the lengths of the "str1" and "str2" respectively

'''



def getLengthOfLCS(str1, str2):



    n = len(str1)

    m = len(str2) 



    # Dynamic programming matrix to store the length of LCS.

    dp = [[0] * (m + 1) for _ in range(n + 1)] 



    # Start traversing through the "str1".

    for i in range(n + 1):

        for j in range(m + 1):

            if (i == 0) or (j == 0):

                # Length of one of the subtring is zero.

                dp[i][j] = 0; 

            elif str1[i - 1] == str2[j - 1]:

                # The last character of both substring matches.

                dp[i][j] = dp[i - 1][j - 1] + 1;

            else:

                # Get the maximum of both possibilities.

                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);

             

    return dp[n][m];

Accepted Answer

Dynamic Programming + Space Optimization

We can observe in the previous approach that the current state depends on one immediate previous row. This suggests using a dynamic programming matrix of 2*M dimension instead of using N*M dimension.

Let DP[ 2 ][ M ] be our dynamic programming matrix to store the length of LCS of the substring.

Now, consider the following steps :

Initialize a variable ‘T’ to zero which denotes the current row of “DP” matrix.

Start traversing the “STR1” using a variable ‘I’

Create a nested loop and start traversing the “STR2” using a variable ‘J’

If either ‘I’ or ‘J’ is zero then DP[T][J] = 0 because one of the strings is empty.

If ( STR1[i-1] == str2[j-1] ) which means the current character of both string matches then it is optimal to include the current character in the LCS. Therefore, find the LCS of the remaining characters of both strings. DP[t][j] = DP[t^1][j-1] + 1

Otherwise, we can not have both STR1[i-1] and str2[j-1] at the end of the LCS which means either of them can be ignored. Now there are two possibilities, either we ignore STR1[i-1] and get the LCS of the rest of the characters and vice versa. We should choose the option which maximises the LCS i.e. DP[t][j] = max(DP[t^1][j], DP[t][j-1])

Now, toggle the ‘T’ i.e. T = (T XOR 1). The reason behind this is we want to use the current row of “DP” matrix in the next iteration.

Now we can get the length of LCS from DP[t^1][M] where ‘M’ is the length of “STR2”.

Space Complexity: O(n)Explanation:

O(M), where ‘M’ is the length of ‘STR2’ respectively.

The only extra space which is being used is the dynamic programming table dp[][] of 2*(M+1) dimension. Thus, the overall space complexity will be O(M).

Time Complexity: O(m*n) - For 2d arraysExplanation:

O(N * M), where ‘N’ and ‘M’ are the length of 'STR1' and ‘STR2’ respectively.

Since we are traversing through both strings using a nested loop. The overall time complexity will be O(N * M).

Python (3.5)

'''

    Time Complexity: O(N * M)

    Space Complexity: O(M)



    where 'N' and 'M' are the lengths of the "str1" and "str2" respectively

'''



def getLengthOfLCS(str1, str2):



    n = len(str1)

    m = len(str2) 



    # Dynamic programming matrix to store the length of LCS.

    dp = [[0] * (m + 1) for _ in range(2)] 



    t = 0

    # Start traversing through the "str1".

    for i in range(n + 1):

        for j in range(m + 1):

            if (i == 0) or (j == 0):

                # Length of one of the subtring is zero.

                dp[t][j] = 0;   

            elif str1[i - 1] == str2[j - 1]:

                # The last character of both substring matches.

                dp[t][j] = dp[t ^ 1][j - 1] + 1;

            else:

                # Get the maximum of both possibilities.

                dp[t][j] = max(dp[t][j - 1], dp[t ^ 1][j]);



        t = t ^ 1;

                        

    return dp[t ^ 1][m];

C++ (g++ 5.4)

/*

    Time Complexity: O(N * M)

    Space Complexity: O(M)



    where 'N' and 'M' are the lengths of the "str1" and "str2" respectively.

*/



int getLengthOfLCS(string & str1, string & str2) {

    int n = str1.size();

    int m = str2.size();



    /* 

        Dynamic programming matrix to store 

        the length of getLengthOfLCS of subString.

    */

    vector < vector < int >> dp(2, vector < int > (m + 1, 0));



    // To traverse the row of "dp".

    int t = 0;



    // Start traversing through the "str1".

    for (int i = 0; i <= n; i++) {

        for (int j = 0; j <= m; j++) {

            if (i == 0 || j == 0) {

                // Length of one of the subtring is zero.

                dp[t][j] = 0;

            } else if (str1[i - 1] == str2[j - 1]) {

                // The last character of both substring matches.

                dp[t][j] = dp[t ^ 1][j - 1] + 1;

            } else {

                // Get the maximum of both possibilities.

                dp[t][j] = max(dp[t][j - 1], dp[t ^ 1][j]);

            }

        }



        // Toggling.

        t = t ^ 1;

    }



    return dp[t ^ 1][m];

}

Java (SE 1.8)

/*

    Time Complexity: O(N * M)

    Space Complexity: O(M)



    where 'N' and 'M' are the lengths of the "str1" and "str2" respectively.

*/



import java.util.ArrayList;



public class Solution {

    public static int getLengthOfLCS(String str1, String str2) {

        int n = str1.length();

        int m = str2.length();



        /* 

            Dynamic programming matrix to store 

            the length of getLengthOfLCS of subString.

        */

        ArrayList < ArrayList < Integer >> dp = new ArrayList < ArrayList < Integer >> (2);



        for (int i = 0; i < 2; i++) {



            dp.add(new ArrayList < Integer > (m + 1));

            for (int j = 0; j <= m; j++) {

                dp.get(i).add(0);

            }

        }



        // To traverse the row of "dp".

        int t = 0;



        // Start traversing through the "str1".

        for (int i = 0; i <= n; i++) {

            for (int j = 0; j <= m; j++) {

                if (i == 0 || j == 0) {

                    // Length of one of the subtring is zero.

                    dp.get(t).set(j, 0);

                } else if (str1.charAt(i - 1) == str2.charAt(j - 1)) {

                    // The last character of both subString matches.

                    dp.get(t).set(j, dp.get(t ^ 1).get(j - 1) + 1);

                } else {

                    // Get the maximum of both possibilities.

                    dp.get(t).set(j, Math.max(dp.get(t).get(j - 1), dp.get(t ^ 1).get(j)));

                }

            }



            // Toggling.

            t = t ^ 1;

        }



        return dp.get(t ^ 1).get(m);

    }

}

You have been given two Strings “STR1” and “STR2” of characters. Your task is to find the length of the longest common subsequence.

A String ‘a’ is a subsequence of a String ‘b’ if ‘a’ can be obtained from ‘b’ by deletion of several (possibly, zero or all) characters. A common subsequence of two Strings is a subsequence that is common to both Strings.

Input Format :

Output Format :

Note:

Constraints :

Top One Convergence Software Developer interview questions & answers

Popular interview questions of Software Developer