Home » Interview coding problems/challenges

# Longest Common Subsequence

**Longest Common Subsequence**: Here, we are going to learn about the solution of Longest Common Subsequence – which is an interview coding questions featured in any rounds of top companies.

Submitted by Radib Kar, on February 20, 2020

**Description:**

This question has been featured in interview rounds of Amazon, MakeMyTrip, VMWare etc.

**Problem statement:**

Given two strings * str1* and

*, find length of the*

**str2****longest common sub-sequence**between them

Let the strings be str1="includehelp" str2="letsinclude" Output will be: Longest common sub-sequence length is 7 The longest common sub-sequence is: "include"

The output is given above where the longest common sub-sequences is in same colour.

**Solution Approach:**

The problem can be solved in a brute-force way. By generating all sub-sequences and checking them whether equal or not. Finally taking the longest common subsequence. But undoubtedly this is not at all computable since generating all sub-sequence is itself exponential and then permutations for checking any two sub-sequences.

The recursive way to solve is

Let,

l_{1}= Length of the first string,str1 l_{2}= Length of the second string,str2 f(l_{1},l_{2}) = Longest common subsequence length for string lengths l1 & l2

Now,

Think of the following example,

Say first string is: **x _{1} x_{2} ... x_{l1}**

And the second string is: **y _{1} y_{2} ... y_{l2}**

Say,

Then obviously we need to find LCS for the remaining part of string and then add 1 for this character match

Else

Maximum of two case

- LCS of the first string leaving character and second string
- LCS of the first string and second string leaving character

Now, we need to recur down to 0. So,

Where base cases are,

If you generate this recursion tree, it will generate many overlapping sub-problems and thus, we need to reduce the re-computing. That’s why we need to convert it into dynamic programming where we will store the output of the sub-problems and we will use it to compute bigger sub-problems.

### Converting to Dynamic programing

1) Initialize dp[l_{1}+1][l_{2}+1] to 0 2) Convert the base case of recursion: for i=0 to l_{1}dp[i][0]=0; for i=0 to l_{2}dp[0][i]=0; 3) Fill the DP table as per recursion. for i=1 to l_{1}//i be the subproblem length for str1 for j=1 to l_{2}//j be the subproblem length for str2 if(str1[i-1]==str2[j-1]) //x_{l1}==y_{l2}dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); end for end for 4) The final output will be dp[l_{1}][l_{2}]

**C++ Implementation:**

#include <bits/stdc++.h> using namespace std; int max(int a, int b) { return (a > b) ? a : b; } int LCS(string str1, string str2) { int l1 = str1.length(); int l2 = str2.length(); int dp[l1 + 1][l2 + 1]; for (int i = 0; i <= l1; i++) dp[i][0] = 0; for (int i = 0; i <= l2; i++) dp[0][i] = 0; for (int i = 1; i <= l1; i++) { for (int j = 1; j <= l2; j++) { if (str1[i - 1] == str2[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[l1][l2]; } int main() { string str1, str2; cout << "Enter first string\n"; cin >> str1; cout << "Enter Second string\n"; cin >> str2; cout << "Longest Common sub-sequence length is: " << LCS(str1, str2) << endl; return 0; }

**Output**

Enter first string includehelp Enter Second string letsincludeus Longest Common sub-sequence length is: 7

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions