Minimum shift Operations

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
9 upvotes
Asked in company
Bank Of America

Problem statement

Let’s define a shift operation on a string ‘S’ as picking any single character from the string and pushing it at the front of the string. For example, S = “ABCD”. Let’s pick the character ‘C’. So, after the shift operation string ‘S’ becomes “CABD”.

You are provided with the two strings named 'S1' and 'S2'. You have to calculate whether it is possible to convert 'S1' to 'S2'. If possible, you have to find the minimum number of shift operations required to do so.

Note: 
Both the strings have only uppercase English alphabets. You can only perform shift operations to convert 'S1' to 'S2'.
Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

Then the ‘T’ test cases follow.

The first line of each test case contains the string 'S1'.

The second line of each test case contains the string 'S2'.

Output format:

For each test case, the minimum number of shift operations to convert 'S1' to 'S2' is printed (if the conversion is possible). -1 is printed when the conversion is not possible.

The output of each test case is printed in a separate line.
Constraints : 
1 <= T <= 10
1 <= |S1| <= 50000
1 <= |S2| <= 50000

where ‘T’ is the number of test cases, |S1| is the length of the 'S1' string, and |S2| is the length of the 'S2' string.

Time Limit: 1 sec

Sample Input 1:

2
ABCD
BACD
EFEF
FEEF

Sample Output 1:

1
1

Explanation of Sample Input 1:

In the first test case, performing shift operation on character ‘B’ only in S1 can give the desired result. S1 = “ABCD”, apply shift operation on ‘B’. New S1 = “BACD”.

In the second test case, performing shift operation on character ‘F’ (first occurrence) only in S1 can give the desired result. S1 = “EFEF”, apply shift operation on ‘F’. New S1 = “FEEF”.

Sample Input 2:

3
ABCD
ACBD
EEGG
EEGG
JKLM
JKMN

Sample Output 2:

2
0
-1

Explanation of Sample Input 2:

In the first test case, perform shift operation two times. First on character ‘C’ and then on character ‘A’.

In the second test case, there is no need to perform shift operations as strings are already the same.

In the third test case, there is no way to convert S1 to S2.
Hint

Try to make strings equal from ending to beginning.

Approaches (1)
Greedy approach

To check the possibility of conversion, all we have to do is just check whether each character’s frequency is exactly equal in both the strings or not. 

 

For the minimum shift operations, the idea is to calculate the difference between the characters’ occurrences from the end of the strings. Set two pointers on both strings (one on each). Initially, point both the pointers to the last character of both the strings. Now, decrement both the pointers’ values by one simultaneously until you find the different characters corresponding to the pointers.

 

After this, decrement the value (by one) of the pointer (set on string S1) and increment the counter by one until you again find the same character as pointing by the second pointer (pointer on string S2). You must have to stop your iteration whenever you reach the very beginning of string S1.

 

Algorithm: 

  1. Make a vector of size 26 to hold each character’s frequency in both strings. You can increment the frequency count by 1 if a particular character occurs in S1 and decrement by 1 if it occurs in S2.
  2. If found the difference in frequency of any character, return -1.
  3. While p1 >= 0
    • If, S1[p1] == S2[p2] , decrement p1 and p2 by one.
    • Else, decrement p1 and increment the counter by one.
  4. Return the value of the counter.
Time Complexity

O(N), where ‘N’ is the length of the string S1.

 

We have set our condition as p1 >= 0 in the while loop. So, we will only traverse string S1 from the last character to the first character. It leads to the time complexity of O(N). Thus, the overall time complexity is O(N).

Space Complexity

O(1).

 

We are using only two vectors of size 26 (constant). Thus, the space complexity required is constant. Hence, the overall Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Minimum shift Operations
Full screen
Console