Print Longest Common Subsequence

Hard
0/120
profile
Contributed by
218 upvotes
Asked in company
HashedIn by Deloitte

Problem statement

You are given two strings ‘s1’ and ‘s2’.


Return the longest common subsequence of these strings.


If there’s no such string, return an empty string. If there are multiple possible answers, return any such string.


Note: 
Longest common subsequence of string ‘s1’ and ‘s2’ is the longest subsequence of ‘s1’ that is also a subsequence of ‘s2’. A ‘subsequence’ of ‘s1’ is a string that can be formed by deleting one or more (possibly zero) characters from ‘s1’.


Example: 
Input: ‘s1’  = “abcab”, ‘s2’ = “cbab”

Output: “bab”

Explanation:
“bab” is one valid longest subsequence present in both strings ‘s1’ , ‘s2’.


Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains two integers ‘n’ and ‘m’, length of ‘s1’ and length of ‘s2’.

The second line of the input contains the string ‘s1’.

The third line of the input contains the string ‘s2’.


Output Format: 
Return a string which is the longest common subsequence of ‘s1’ and ‘s2’. If there’s no such string return an empty string.


Note 
You don’t need to print anything, it has already been taken care of, just complete the given function. ‘1’ will be printed if the given subsequence is present in both the strings and length of the string is equal to the longest common subsequence and ‘0’ otherwise.
Sample Input 1:
5 6
ababa
cbbcad


Expected Answer:
"bba"


Output on console:
1


Explanation of sample output 1:
“bba” is only possible longest subsequence present in both s1 = “ababa” and s2 = “cbbcad”. '1' is printed if the returned string is equal to "bba".


Sample Input 2:
3 3
xyz
abc


Expected Answer:
""


Output on console:
1


Explanation of sample output 2:
There’s no subsequence of ‘s1’ that is also present in ‘s2’. Thus an empty string is returned and '1' is printed.


Expected Time Complexity:
Try to solve this in O(n*m). Where ‘n’ is the length of ‘s1’ and ‘m’ is the length of ‘s2’.


Constraints:
1 <= n, m <= 10^3

Time Limit: 1 sec
Hint

Think about transitions used during calculating length of LCS using dynamic programming.

Approaches (1)
Precalculating Length of LCS

Approach:

We will first calculate the length of LCS using dynamic programming. While calculating LCS using dynamic programming we use the following transitions:

  • If s1[i] == s2[j]
    • dp[i][j] = 1 + dp[i-1][j-1].
  • else
    • dp[i][j]  = max(dp[i-1][j], dp[i][j-1]).


 

We will start from i = ‘n’, j = ‘m’ where ‘n’ is length of ‘s1’ and ‘m’ is length of ‘s2’ (we are taking indices to be ‘1’ indexed) .

  • If s1[i] != s2[j], then dp[i][j] got its value from either dp[i-1][j] or dp[i][j-1]. So, if dp[i-1][j] > dp[i][j-1], we will decrement ‘i’, else we will decrement ‘j’.
  • If s1[i] == s2[j], then the current character ‘s1[i]’ is a part of LCS and dp[i][j] got its value from dp[i-1][j-1]. So we will push this character to the final answer and decrement both ‘i’ and ‘j’.

We will keep repeating the above steps until both ‘i’ and ‘j’ are > 0. Then reverse the string we got from the above process, and we have our answer.


 

The steps are as follows:

function calculateLCS(int n, int m, string s1, string s2, vector<vector<int>> &dp)

  1. for ‘i’ from ‘1’ to ‘n’
    1. for ‘j’ from ‘1’ to ‘m’
      1. if ( s1[i] == s2[j] )
        1. dp[i][j] = dp[i-1][j-1] + 1
      2. else
        1. dp[i][j] = max(dp[i-1][j],dp[i][j-1])

function findLCS(int n, int m, string s1, string s2)

  1. Initialize 2D vector ‘dp’.
  2. calculateLCS(n,m,s1,s2,dp)
  3. Initialize ‘i’ = ‘n’ and ‘j’ = ‘m’
  4. Initialize string ‘ans’ and an empty string
  5. while(i > 0 && j > 0)
    1. if(s1[i] == s2[j])
      1. ans.push_back(‘s1[i]’)
      2. i--, j--
    2. else
      1. if (dp[i-1][j] > dp[i][j-1])
        1. i--
      2. else
        1. j--
  6. reverse(ans)
  7. return ans

 

Time Complexity

O(n*m), where ‘n’ is the length of ‘s1’ and ‘m’ is the length of ‘s2’.


 

While calculating values of dp array we are iterating via ‘i’ from 1 to ‘n’, and for each value of ‘i’ we are iterating from ‘1’ to ’m’ via ‘j’.


 

Hence, the time complexity is O(n*m).

Space Complexity

O(n*m), where ‘n’ is the length of ‘s1’ and ‘m’ is the length of ‘s2’.


 

We are using a 2D array ‘dp’ of size n*m.


 

Hence, the space complexity is O(n*m).

Code Solution
(100% EXP penalty)
Print Longest Common Subsequence
Full screen
Console