PROBLEM LINK:
Author: Anita Acha George
Tester: Alex Mathew
Editorialist: Alex Mathew
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
OBSERVATION
PROBLEM:
Sandeep, Ashok and Mohan were sitting together. Sandeep and Ashok decided to pass their free time by quizing each other. Ashok asked Sandeep to think of any word. Once Sandeep did this, Ashok thought of a word of his own. He then proceeded to convert his word into Ashok’s word by shifting the alphabets of Sandeep’s word. They then kept doing this by interchanging their roles.
Mohan didnt know whether the answers being given were correct or not. So he, being an awesome programmer decided to write a code to check all the answers.
Given two strings A and B, the task is to convert A to B if possible. The only operation that is allowed is to put any character from A and insert it at front. Find if it’s possible to convert the string. If yes, then output minimum no. of operations required for transformation.
EXPLANATION:
This problem can be divided into two parts.
-
We can find out the cases in which the conversion is not possible. In the first case the length of the two strings will not be equal. In the second case the occurrence of each character in the string may vary. If any of these two conditions are satisfied then we can confirm that conversion is not possible.
-
If the above case is not true then we can start matching from the last characters of both strings. If the last characters match, then our task reduces to n-1 where n is the length of the string. If the last characters don’t match, then find the position of the second string’s mismatching character in the first string. The difference between the two positions indicates that those many characters of the first string must be moved before the current characters of the first string.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.