Problem title
Difficulty
Avg time to solve

Rearrange odd and even places
Moderate
--
Idempotent Matrix
Easy
--
Longest Common Prefix
Moderate
30 mins
Water Droplet Mixing
Easy
28 mins
Distinct Islands
Moderate
25 mins
Convert Decimal To Irreducible Fraction
Easy
25 mins
Delete N nodes after M nodes of a linked list
Moderate
30 mins
Minimum Number of Platform Needed
Easy
23 mins
Break Number
Moderate
35 mins
Modify Matrix
Moderate
40 mins
3

Longest Common Subsequence

Difficulty: MEDIUM
Contributed By
Priyaraj |Level 1

Problem Statement

You have been given two Strings “STR1” and “STR2” of characters. Your task is to find the length of the longest common subsequence.

A String ‘a’ is a subsequence of a String ‘b’ if ‘a’ can be obtained from ‘b’ by deletion of several (possibly, zero or all) characters. A common subsequence of two Strings is a subsequence that is common to both Strings.

Input Format :
The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows. 

The first input line of each test case contains two space-separated Strings “STR1” and “STR2” representing two Strings. 
Output Format :
For each test case, print the length of the longest common subsequence. 

Print the output of each test case in a separate line. 
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function. 
Constraints :
1 <= T <= 50 
1 <= |STR1| <= 10^2
1 <= |STR2| <= 10^2

Where |STR1| and |STR2| denote the length of “STR1” and “STR2” respectively. 

Time Limit: 1 sec 
Sample Input 1 :
2
abc cadb
pqr tpuqvr
Sample output 1 :
2
3
Explanation For Sample Input 1 :
For the first test case, the longest common subsequence is “ab” and its length is 2.

For the second test case, the longest common subsequence is “pqr” and its length is 3.    
Sample Input 2 :
2
a b
a a
Sample output 2 :
0
1
Explanation For Sample Input 2 :
For the first test case, any non-empty common subsequence doesn’t exist. 

For the second test case, the longest common subsequence is “a” and its length is 1.    
Reset Code
Full screen
copy-code
Console