Update appNew update is available. Click here to update.

Shortest Supersequence

Last Updated: 8 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

Given two arrays ‘SMALL’ and ‘LARGE’, you need to find the length of the shortest sub-array of ‘LARGE’ array, that contains all elements of the ‘SMALL’ array. It is given that elements in the ‘SMALL’ sub array can be in any order.

Note
All the elements in the ‘SMALL’ array are distinct.    
For Example
Let us say 'SMALL' = [ 3,6 ] and 'LARGE' = [ 8, 6, 9, 3, 1, 2, 6].

Subarray [ 1,3 ] (from index 1 to index 3) and [ 3,6 ] have all the elements that are present 

In ‘SMALL’ array. The length of the sub-array [ 1, 3 ] is shorter. Therefore required answer = 3
Input Format
The first line contains a single integer ‘T’ denoting the number of test cases.

The first line of each test contains two integers ‘M’ and ‘N’ - the number of elements in the ‘LARGE’ and ‘SMALL’ array respectively.

The third line of each test case contains ‘M’ space-separated integers that make up ‘LARGE’.

The fourth line of each test case contains ‘N’ space-separated integers that makeup ‘SMALL’.
Output Format
For each test case, print an integer denoting the length of the shortest sub-array of ‘LARGE’ having all elements of ‘SMALL’.

If no such subarray exists, return ‘-1’.
Note
You are not required to print anything; it has already been taken care of. Just implement the function and return the matrix.
Constraints
1 <= T <= 50
1 <= M,N <= 10^4
1 <= LARGE[ i ] , SMALL[ i ] <=10^8

Time Limit: 1 sec