Last Updated: 5 Feb, 2021
Minimum shift Operations
Moderate
Asked in company
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'.
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
Approaches
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:
- 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.
- If found the difference in frequency of any character, return -1.
- While p1 >= 0
- If, S1[p1] == S2[p2] , decrement p1 and p2 by one.
- Else, decrement p1 and increment the counter by one.
- Return the value of the counter.