Minimum number of given operations required to make two strings equal | C ++ implementation of the above approach ; Function to return the minimum number of operations to convert string A to B ; If both the strings are equal then no operation needs to be performed ; store the position of ' _ ' ; to store the generated string at every move and the position of ' _ ' within it ; vis will store the minimum operations to reach that particular string ; minimum moves to reach the string ss ; if ' _ ' can be swapped with the character on it 's left ; swap with the left character ; if the string is generated for the first time ; if generated string is the required string ; update the distance for the currently generated string ; restore the string before it was swapped to check other cases ; swap ' _ ' with the character on it 's right this time ; if ' _ ' can be swapped with the character ' i + 2' ; if ' _ ' can be swapped with the character at ' i + 2' ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minOperations ( string s , string f ) { if ( s == f ) return 0 ; unordered_map < string , int > vis ; int n ; n = s . length ( ) ; int pos = 0 ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { if ( s [ i ] == ' _ ' ) { pos = i ; break ; } } queue < pair < string , int > > q ; q . push ( { s , pos } ) ; vis [ s ] = 0 ; while ( ! q . empty ( ) ) { string ss = q . front ( ) . first ; int pp = q . front ( ) . second ; int dist = vis [ ss ] ; q . pop ( ) ; if ( pp > 0 ) { swap ( ss [ pp ] , ss [ pp - 1 ] ) ; if ( ! vis . count ( ss ) ) { if ( ss == f ) { return dist + 1 ; break ; } vis [ ss ] = dist + 1 ; q . push ( { ss , pp - 1 } ) ; } swap ( ss [ pp ] , ss [ pp - 1 ] ) ; } if ( pp < n - 1 ) { swap ( ss [ pp ] , ss [ pp + 1 ] ) ; if ( ! vis . count ( ss ) ) { if ( ss == f ) { return dist + 1 ; break ; } vis [ ss ] = dist + 1 ; q . push ( { ss , pp + 1 } ) ; } swap ( ss [ pp ] , ss [ pp + 1 ] ) ; } if ( pp > 1 && ss [ pp - 1 ] != ss [ pp - 2 ] ) { swap ( ss [ pp ] , ss [ pp - 2 ] ) ; if ( ! vis . count ( ss ) ) { if ( ss == f ) { return dist + 1 ; break ; } vis [ ss ] = dist + 1 ; q . push ( { ss , pp - 2 } ) ; } swap ( ss [ pp ] , ss [ pp - 2 ] ) ; } if ( pp < n - 2 && ss [ pp + 1 ] != ss [ pp + 2 ] ) { swap ( ss [ pp ] , ss [ pp + 2 ] ) ; if ( ! vis . count ( ss ) ) { if ( ss == f ) { return dist + 1 ; break ; } vis [ ss ] = dist + 1 ; q . push ( { ss , pp + 2 } ) ; } swap ( ss [ pp ] , ss [ pp + 2 ] ) ; } } } int main ( ) { string A = " aba _ a " ; string B = " _ baaa " ; cout << minOperations ( A , B ) ; return 0 ; }