Minimum operation needed to convert to the given string

Moderate

0/80

Average time to solve is 26m

Contributed by

57 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 :

Hint 1

Try to think when it is possible to convert str1 into str2 and if it is possible, then how to do it in a greedy way to minimize the operations.

Approaches (1)

Approach 1

Greedy Approach

We will do the two-pointer approach, Initialize the first pointer to the start of str1 and the second pointer to the start of the str2.
Now increase the first pointer till the character pointed by the first pointer in str1 matches the character at the second pointer in str2. And the number of character which did not match should be placed at the end of str1. Therefore increase our answer by how many times we needed to increase the first pointer.
Now character pointed by both the pointer is the same so simply increase both pointers as they are same. And perform this while both the pointer do not exhaust the str1 and str2 respectively.
One thing to note is that all the characters which did not match would be placed at the end optimally so that the cost will be equal to the unmatched characters with the prefix of str2.

Time Complexity

O(N+M) where N is the size of the first string and M is the size of the second string.

We are traversing both the strings only once.Thus time complexity is O(N+M).

Space Complexity

O(1), as constant extra space, is used.

(100% EXP penalty)

Minimum operation needed to convert to the given string

Console