Minimum number of operations required to make two strings equal | C ++ implementation to find the minimum number of operations to make two strings equal ; Function to find out parent of an alphabet ; Function to merge two different alphabets ; Merge a and b using rank compression ; Function to find the minimum number of operations required ; Initializing parent to i and rank ( size ) to 1 ; We will store our answerin this vector ; Traversing strings ; If they have different parents ; Find their respective parents and merge them ; Store this in our Answer vector ; Number of operations ; Driver Code ; Two strings S1 and S2 ; Function Call
#include <bits/stdc++.h> NEW_LINE #define MAX  500001 NEW_LINE using namespace std ; int parent [ MAX ] ; int Rank [ MAX ] ; int find ( int x ) { return parent [ x ] = parent [ x ] == x ? x : find ( parent [ x ] ) ; } void merge ( int r1 , int r2 ) { if ( r1 != r2 ) { if ( Rank [ r1 ] > Rank [ r2 ] ) { parent [ r2 ] = r1 ; Rank [ r1 ] += Rank [ r2 ] ; } else { parent [ r1 ] = r2 ; Rank [ r2 ] += Rank [ r1 ] ; } } } void minimumOperations ( string s1 , string s2 ) { for ( int i = 1 ; i <= 26 ; i ++ ) { parent [ i ] = i ; Rank [ i ] = 1 ; } vector < pair < char , char > > ans ; for ( int i = 0 ; i < s1 . length ( ) ; i ++ ) { if ( s1 [ i ] != s2 [ i ] ) { if ( find ( s1 [ i ] - 96 ) != find ( s2 [ i ] - 96 ) ) { int x = find ( s1 [ i ] - 96 ) ; int y = find ( s2 [ i ] - 96 ) ; merge ( x , y ) ; ans . push_back ( { s1 [ i ] , s2 [ i ] } ) ; } } } cout << ans . size ( ) << endl ; for ( int i = 0 ; i < ans . size ( ) ; i ++ ) cout << ans [ i ] . first << " - > " << ans [ i ] . second << endl ; } int main ( ) { string s1 , s2 ; s1 = " abb " ; s2 = " dad " ; minimumOperations ( s1 , s2 ) ; return 0 ; }