Hi this was the question on Directi hiring coding challenge over same plateform ‘codechef’.I was able to solve this as there is limit on answer as it would’nt be greater than 30.
But is it possible to find solution in general.
Given two strings I and F, where I is the initial state and F is the final state. Each state will contain ‘a’,’b’ and only one empty slot represented by ‘_’. Your task is to move from the initial state to final state with minimum number of operation.
Allowed operations are
- You can swap empty character with any adjacent character. (For example ‘aba_ab’ can be converted into ‘ab_aab’ or ‘abaa_b’).
- You can swap empty character with next to adjacent character only if adjacent character is different from next to adjacent character. (For example ‘aba_ab’ can be converted into ‘a_abab’ or ‘ababa_’, but ‘ab_aab’ cannot be converted to ‘abaa_b’, because ‘a’ cannot jump over ‘a’).
Input
The first line contains single integer T – the number of test cases (less than 25). T test cases follow.
Each test case contains two string I and F in two different lines, where I is the initial state and F is the final state. I and F may be equal. Their length will always be equal. Their length will be at least 2. Their length will never be more than 20.
Output
For each test case output a single line containing the minimum number of steps required to reach the final state from the initial state. You can assume it is always possible to reach the final state from the initial state. You can assume that no answer is more than 30.