Minimum operation needed to convert to the given string

Moderate

0/80

Average time to solve is 26m

Contributed by

53 upvotes

Asked in companies

Problem statement

You are given two strings 'str1' and 'str2'. Find the minimum operations required to convert str1 into str2.

An Operation is defined as:

A character from an index of a string(str1) is put at the end of it, is defined as a single operation.

Note :

You cannot perform any operation on the string, str2.

Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first line of input contains a single integer 'T' denoting the number of test cases or queries to be run. 

The first line of each test case contains a string, representing  str1. 

The second line of each test case contains a string, representing str2.

Output Format :

For each test case/query, print the minimum number of operations required to convert str1 into str2. Print -1 if it is not possible.

Output for every test case will be printed in a separate line.

Note :

You are not required to print the output explicitly, it has already been taken care of. Just implement the function.

Input strings contain only lower case and uppercase letters and do not contain blank spaces.

Constraints :

1 <= T <= 10
1 <= N <= 10^5
1 <= M <= 10^5
Where N and M are the lengths of the input strings 'str1', and 'str2' respectively.

Time Limit: 1 sec

Sample Input 1 :

2
ABC
ACB
AbcD
bcAD

Sample Output 1 :

1
2

Explanation of Sample Input 1:

For the first test case, we can move 'B' to the end of str1 so str1 becomes 'ACB' which is equal to the str2. Hence 1 operation was needed.

For the second test case, move 'A' to the end of str1 so new string becomes 'bcDA', Now move 'D' to the end so we have now str1 = 'bcAD' which is equal to the str2. Hence 2 operations were needed.

Sample Input 2 :

1
IFDfxPCdNvCNXPe
NFfPICxeCNDdXPv

Sample Output 2 :

Console