 New update is available. Click here to update.

# Longest Common Subsequence

Contributed by
Deep Mavani
Last Updated: 23 Feb, 2023
Medium 0/80
Avg time to solve 39 mins Share 97 upvotes

## Problem Statement

#### For a string 'str'(per se) of length K, the subsequences are the strings containing characters in the same relative order as they are present in 'str,' but not necessarily contiguous. Subsequences contain all the strings of length varying from 0 to K.

##### Example :
``````Subsequences of string "abc" are:  ""(empty string), a, b, c, ab, bc, ac, abc.
``````
Detailed explanation ( Input/output format, Notes, Images ) ##### Constraints :
``````0 <= M <= 10 ^ 3
0 <= N <= 10 ^ 3

Time Limit: 1 sec
``````
##### Sample Input 1 :
``````adebc
``````
##### Sample Output 1 :
``````3
``````
##### Explanation of the Sample Output 1 :
``````Both the strings contain a common subsequence 'adb', which is the longest common subsequence with length 3.
``````
##### Sample Input 2 :
``````ab
defg
``````
##### Sample Output 2 :
``````0
``````
##### Explanation of the Sample Output 2 :
``````The only subsequence that is common to both the given strings is an empty string("") of length 0.
``````  Auto Console