# Longest Common Subsequence using Dynamic programming (DP)

Here we are going to learn how to **find length of longest common subsequence in two strings**?

Submitted by Ritik Aggarwal, on November 08, 2018

**Problem:** You are given two string of length **N** and **M** respectively. You have to **find the length longest common subsequence**.

**Constraints:**

1 <= N <= 10^3 1 <= M <= 10^3

**Example:**

Input: helo heoa Output: 3

**Explanation of the problem:**

In the sample input given above, **"heo"** from **"helo"** and **"heo"** from **"heoa"** is the longest subsequence so the length of Longest Common Subsequence is **3**.

**Solution:**

Before going to the code we can see that recursive solution will show time limit exceeded. As recursive solution has time complexity as **O(2^(N+M))**. So we definitely have to use **dp**. I will be using a 2D- matrix in which **j ^{th}** cell of

**i**row represent the

^{th}**longest common subsequence**in the string 1 (

**i**index to the end) and string 2 (

^{th}**j**index till end).

^{th}**So now is the code of above approach:**

#include <iostream> using namespace std; int LCS(string s1, string s2){ int dp[s1.length()+1][s2.length() + 1] = {0}; for(int row = s1.length() - 1;row>=0;row--){ for(int col = s2.length()-1;col>=0;col--){ if(s1[row] == s2[col]){ dp[row][col] = dp[row + 1][col + 1] + 1; }else{ dp[row][col] = max(dp[row+1][col], dp[row][col+1]); } } } return dp[0][0]; } int main(){ string s1, s2; cin >> s1; cin >> s2; cout << LCS(s1,s2) << endl; return 0; }

**Output**

helo heoa 3

I have used the bottom approach and the time complexity of this approach is **O(N * M)**.

**Quick links:**

C FAQ(s)
C Advance programs
C/C++ Tips & Tricks
Puzzles
JavaScript
CSS
Python
Linux Commands
PHP
Android
Articles
More...

**Featured post:**

Introduction to Linux (Its modes, Safety, Most popular Applications)

Linux Best Distribution Software (Distros) of 2018

Was this page helpful? Please share with your friends...

Are you a blogger? Join our Blogging forum.

Comments and Discussions