Problem title
Difficulty
Avg time to solve

Form a Triangle
Easy
15 mins
Longest Mountain Subarray
Easy
10 mins
Selection Sort
Easy
15 mins
Find Four Elements That Sums To A Given Value
Moderate
10 mins
Delete middle element from stack
Easy
15 mins
Factorial of a Number
Easy
--
Longest Common Subsequence
Moderate
39 mins
Encode the Message
Easy
18 mins
Sudoku Solver
Hard
25 mins
Word Break-1
Moderate
36 mins
36

Longest Common Subsequence

Difficulty: MEDIUM
Contributed By
Avg. time to solve
39 min

Problem Statement

Given two strings, 'S' and 'T' with lengths 'M' and 'N', find the length of the 'Longest Common Subsequence'.

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.
Input format :
The first line of input contains the string 'S' of length 'M'.

The second line of the input contains the string 'T' of length 'N'.
Output format :
Return the length of the Longest Common Subsequence.
Constraints :
0 <= M <= 10 ^ 3
0 <= N <= 10 ^ 3

Time Limit: 1 sec
Sample Input 1 :
adebc
dcadb
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.
Reset Code
Full screen
copy-code
Console