Last Updated: 18 Jun, 2023

Print Longest Common Subsequence

Hard

Asked in company

Solve now

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’.

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.

Solve now

Approaches

01 Approach

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)

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)

Initialize 2D vector ‘dp’.
calculateLCS(n,m,s1,s2,dp)
Initialize ‘i’ = ‘n’ and ‘j’ = ‘m’
Initialize string ‘ans’ and an empty string
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--
reverse(ans)
return ans

Solve now