Update appNew update is available. Click here to update.

Minimum Window Substring

Posted: 4 Mar, 2021
Difficulty: Hard


Try Problem

You are given two strings ‘A’ and ‘B’. Your task is to find a substring ‘S’ of ‘A’ such that the following conditions hold true :

You can make ‘B’ from ‘S’ by removing some characters and rearranging some characters zero or more times.

Length of ‘S’ must be minimum possible.

Note :

If no such substring exists then you need to print -1, else print the length of the substring ‘S’.

Input Format :

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains two space-separated strings ‘A’ and ‘B’.

Output Format :

For each test case, print -1 if no such substring exists, else print length of the required substring.

The output of each test case will be printed in a separate line.

Constraints :

1 <= T <= 5
1 <=  |A| = |B| <= 3000
Both A, B contain only lowercase English letters.

Where |A| and |B| are the length of strings.

Time Limit: 1 sec

Note :

 You do not need to print anything, it has already been taken care of. Just implement the given function.